Dijkstra算法解决了有向图上带正权值的单源最短路径问题，其运行时间要比Bellman-Ford算法低，但适用范围比Bellman-Ford算法窄。
迪杰斯特拉提出的按路径长度递增次序来产生源点到各顶点的最短路径的算法思想是：对有n个顶点的有向连通网络G=(V, E)，首先从V中取出源点u0放入最短路径顶点集合U中，这时的最短路径网络S=({u0}, {}); 然后从uU和vV－U中找一条代价最小的边(u*, v*)加入到S中去，此时S=({u0, v*}, {(u0, v*)})。每往U中增加一个顶点，则要对V－U中的各顶点的权值进行一次修正。若加进v*作为中间顶点，使得从u0到其他属于V－U的顶点vi的路径不加v*时最短，则修改u0到vi的权值，即以(u0, v*)的权值加上(v*, vi )的权值来代替原(u0, vi )的权值，否则不修改u0到vi的权值。接着再从权值修正后的V－U中选择最短的边加入S中，如此反复，直到U=V为止。
上面的说明都很抽象，下面图解算法思想：
原始图为：
寻找最短路径的过程如下：
vc28MTMuMTYoIGYgKaGjPGJyPgo8L3A+CjxwPjxzdHJvbmc+vt/M5bXEs8zQ8sq1z9bI58/Co7o8L3N0cm9uZz48L3A+CjxwPjwvcD4KPHByZSBjbGFzcz0="brush:java;">#include#define M 12//边数#define N 6//顶点数#define MAX 10000void 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; imax, 以保证值为?的顶点也能加入U */ for( j=0; jD[k]+dist[k][j]) ) /* 调整V－U中各顶点的距离值 */ {D[j]=D[k]+dist[k][j]; p[j]=k+1; /* k是j的前趋 */ } } /* 所有顶点已扩充到U中 */ for( i=0; i
结果显示如下：
注：如果程序出错，可能是使用的开发平台版本不同，请点击如下链接： 解释说明
