【算法导论】单源最短路径之Dijkstra算法

​ Dijkstra算法解决了有向图上带正权值的单源最短路径问题，其运行时间要比Bellman-Ford算法低，但适用范围比Bellman-Ford算法窄。

迪杰斯特拉提出的按路径长度递增次序来产生源点到各顶点的最短路径的算法思想是：对有$n$个顶点的有向连通网络$G=(V, E)$，首先从$V$中取出源点$u_0$放入最短路径顶点集合$U$中，这时的最短路径网络$S=({u0}, {\emptyset})$; 然后从$u\in U$和$v\in V-U$中找一条代价最小的边$(u^\star, v^\star)$加入到$S$中去，此时$S=({u_0, v^\star}, {(u_0, v^\star)})$。每往$U$中增加一个顶点，则要对$V-U$中的各顶点的权值进行一次修正。若加进$v^\star$作为中间顶点，使得从$u_0$到其他属于$V-U$的顶点$v_i$的路径不加$v^\star$时最短，则修改$u_0$到$v_i$的权值，即以$(u_0, v^\star)$的权值加上$(v^\star, v_i)$的权值来代替原$(u_0, v_i)$的权值，否则不修改$u_0$到$v_i$的权值。接着再从权值修正后的$V-U$中选择最短的边加入$S$中，如此反复，直到$U=V$为止。

上面的说明都很抽象，下面图解算法思想：

原始图为：

寻找最短路径的过程如下：

​ 对第一个图中的有向网络按以上算法思想处理，所求得的从源点$F$到其余顶点的最短路径的过程如上图所示。其中单圆圈表示$U$中的顶点，而双圆圈表示$V-U$中的顶点。连接$U$中两个顶点的有向边用实线表示，连接$U$和$V-U$中两个顶点的有向边用虚线表示。圆圈旁的数字为源点到该顶点当前的距离值。
​ 初始时，$S$中只有一个源点$F$，它到$V-U$中各顶点的路径如上图(a)所示；选择图(a)中最小代价边$(F,B)$，同时由于路径$(F, A)$大于$(F, B, A)$和$(F, C)$大于$(F, B, C)$，进行相应调整可得到图(b)；选择图(b)中的最小代价边$(B, C)$，同时由于$(F, B, A)$大于$(F, B, C, A)$，进行相应调整可得到图(c)；选择图(c)中最小代价边$(C, A)$即可得到图(d)；选择图(d)中最小代价边$(F, D)$ 即可得到图(e); 最后选择$(F, E)$即可得到图( f )。

具体的程序实现如下：

#include<stdio.h>
#define M 12//边数
#define N 6//顶点数
#define MAX 10000

void Dijkstra(int v, int dist[][N],int D[N],int p[N],int s[N]) ;
int flag[N]={0};
int flag1=0;
int flag2=0;
typedef struct
{
	int startvex;
	int endvex;
	int length;
}edge;//边的结构体
edge T[M];
void main()
{
	int dist[N][N]={{0,6,MAX,8,MAX,MAX},//图的邻接矩阵
					{18,0,7,MAX,MAX,10},
					{9,MAX,0,15,MAX,MAX},
					{MAX,MAX,12,0,MAX,MAX},
					{MAX,MAX,4,MAX,0,MAX},
					{24,5,MAX,25,MAX,0}};
	int D[N]={0};
	int p[N]={0};
	int s[N]={0};
	int num=0;
    Dijkstra(5,dist,D, p,s) ;
}


 void Dijkstra(int v, int dist[][N],int D[N],int p[N],int s[N]) 
 { 	int i, j, k, v1, min, max=10000, pre; 	/* Max中的值用以表示dist矩阵中的值 */
	v1=v; 
	for( i=0; i<N; i++)              /* 各数组进行初始化 */
	{	D[i]=dist[v1][i]; 
		if( D[i] != MAX )  p[i]= v1+1; 
		else p[i]=0; 
		s[i]=0; 
	}

	s[v1]=1;     		             /* 将源点送U */
	  for( i=0; i<N-1; i++) 	 /* 求源点到其余顶点的最短距离 */
	{	min=10001;    /* min>max, 以保证值为的顶点也能加入U */
		for( j=0; j<N-1; j++)
			  if ( ( !s[j] )&&(D[j]<min) )  		/* 找出到源点具有最短距离的边 */
		  		{min=D[j]; 
						k=j; 
		 			}
				s[k]=1;  /* 将找到的顶点k送入U */	
	for(j=0; j<N; j++)
	 if ( (!s[j])&&(D[j]>D[k]+dist[k][j]) ) /* 调整V－U中各顶点的距离值 */
		{D[j]=D[k]+dist[k][j]; 
		p[j]=k+1;                  	/* k是j的前趋 */
				}
			}                           	/*  所有顶点已扩充到U中 */
			for( i=0; i<N; i++)
			{
				printf(" %d : %d ", D[i], i);
				pre=p[i]; 
			while ((pre!=0)&&(pre!=v+1))
			{	printf ("<- %d ", pre-1); 
				pre=p[pre-1]; 
			}
			printf("<-%d \n", v); 
		}
}

结果显示如下：