首页 > 其他 > 详细

好记的迪杰斯特拉算法

时间:2014-08-13 18:54:57      阅读:321      评论:0      收藏:0      [点我收藏+]
好记的迪杰斯特拉算法

核心代码

       不包括花括号的话10行代码.set[]代表顶点集合S,算法的核心思想就是不断根据贪心算法把距离集合S最近的顶点加到集合中.
dis则是距离,源点离各结点的距离.
	for(i=1;i<N;i++)
	{
		Min=65535;		
		for(j=0;j<N;j++)
		{
			if(!set[j]&&dis[j]<Min)
			{
				k=j;
				Min=dis[j];
			}
		}
		set[k]=1;		
		for(j=0;j<N;j++)
		{
			if(!set[j]&&(Min+arc[k][j]<dis[j]))
				dis[j]=Min+arc[k][j];
		}
	}

记下上面的代码后,我们要做的就是倆个初始化,一个是图的初始化

const int N=9,INF=65535;
int vexs[N];
int arc[N][N];

void init()
{
	//初始化图
	for(int i = 0; i < N; i++)
	{
		for(int j = i; j < N; j++)
		{
			arc[i][j] =INF;
		}
	}
	arc[0][1]=1;
	arc[0][2]=5; 
	arc[1][2]=3; 
	arc[1][3]=7; 
	arc[1][4]=5; 

	arc[2][4]=1; 
	arc[2][5]=7; 
	arc[3][4]=2; 
	arc[3][6]=3; 
	arc[4][5]=3;

	arc[4][6]=6;
	arc[4][7]=9; 
	arc[5][7]=5; 
	arc[6][7]=2; 
	arc[6][8]=7;

	arc[7][8]=4;

	for(int i = 0; i < N; i++)
	{
		for(int j = i; j < N; j++)
		{
			arc[j][i] =arc[i][j];
		}
	}
	for(int i=0;i<N;i++)
		vexs[i]=i;
}

迪杰斯特拉算法的初始化,即选定源节点.

//初始化(这里以V0点开始)
for(i=0;i<N;i++)
{
	set[i]=0;
	dis[i]=arc[0][i];
}
dis[0]=0;
set[0]=1;

给出完整的代码

#include<stdio.h>
const int N=9,INF=65535;
int vexs[N];
int arc[N][N];

void init()
{
	//初始化图
	for(int i = 0; i < N; i++)
	{
		for(int j = i; j < N; j++)
		{
			arc[i][j] =INF;
		}
	}
	arc[0][1]=1;
	arc[0][2]=5; 
	arc[1][2]=3; 
	arc[1][3]=7; 
	arc[1][4]=5; 

	arc[2][4]=1; 
	arc[2][5]=7; 
	arc[3][4]=2; 
	arc[3][6]=3; 
	arc[4][5]=3;

	arc[4][6]=6;
	arc[4][7]=9; 
	arc[5][7]=5; 
	arc[6][7]=2; 
	arc[6][8]=7;

	arc[7][8]=4;

	for(int i = 0; i < N; i++)
	{
		for(int j = i; j < N; j++)
		{
			arc[j][i] =arc[i][j];
		}
	}
	for(int i=0;i<N;i++)
		vexs[i]=i;
}

int main()
{
	init();
	int i,j,k,Min;
	int set[N],dis[N];
	//初始化(这里以V0点开始)
	for(i=0;i<N;i++)
	{
		set[i]=0;
		dis[i]=arc[0][i];
	}
	dis[0]=0;
	set[0]=1;
	//主循环
	for(i=1;i<N;i++)
	{
		Min=65535;
		//把距离v1,v2,v3,....最近的点找出来
		for(j=0;j<N;j++)
		{
			if(!set[j]&&dis[j]<Min)
			{
				k=j;
				Min=dis[j];
			}
		}
		set[k]=1;
		//根据最新找到的最短路径,更新v0点到各节点的最短距离
		for(j=0;j<N;j++)
		{
			if(!set[j]&&(Min+arc[k][j]<dis[j]))
				dis[j]=Min+arc[k][j];
		}
	}
	//输出结果
	for(int i=1;i<N;i++)
		printf("%d ",dis[i]);
}

	

结果

  1 4 7 5 8 10 12 16              

好记的迪杰斯特拉算法,布布扣,bubuko.com

好记的迪杰斯特拉算法

原文:http://blog.csdn.net/u013011841/article/details/38539117

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!