迪杰斯特拉算法：按路径长度递增的次序求解最短路径的方法。从单源点出发查找与单源点连接的最小的边，把该边对应的顶点加入集合V，然后从该顶点开始与原来到其他各顶点的最短路径进行比较，若比原来的路径小，则修改到该顶点的最短路径，否则，不修改。重复该过程，直到所有的顶点都加入集合V。即，单源点到其他所有的顶点的最短路径都已找到。
例如：从图中顶点a开始查找与a相连接的最短的边，即ac，然后把c放入集合V中，然后在其他顶点查找与a,c相连的最短路径，即cf，然后把f,放入集合V中，直到所有的顶点都加入集合V中。
从顶点a开始到其他个顶点的最短距离：
INF----------表示两个顶点不可达
V-------------表示该顶点的最短路径已经查找
S-------------表示图中所有顶点的集合
S-V----------表示图中未找到的顶点集合
vex----------表示这次循环选出的顶点
‘——’-------表示该顶点的最短路径已找到
a到b的最短路径为：a–d--g–b ，22
a到c的最短路径为：a–c，8
a到d的最短路径为：a–d，15
a到e的最短路径为：a–c--f–e，13
a到f的最短路径为：a–c--f，11
a到g的最短路径为：a–d--g，19
算法思想：
1>对初始的路径path[][]和最短距离D[]，以及final[]进行初始化。
注：二维数组path[][]记录从顶点a到其他顶的最短路径中的前驱；用一个D[]的数组记录路径的长度。final[i]=1表示该顶点的最短路径已经找到。
2>查找最短的路径
3>更新最短路径。若加上查找到的最短路径比原来的最短路径要小，则修改到该顶点的最短路径；若大于原来的最短路径，则不变。
void Dijkstra(MGraph G, int v0, int path[][MAX], int D[]){//final[vs]=1，表示v0到vs的最短路径已找到 //path[vs][v]=1，则v是：从v0到vs当前的最短路径上顶点的下标（存放vs之前的路径） //D[vs]，表示从v0到vs的最短路径的距离 int v, w, i, t; int final[MAX];int min; //初始化 for ( v = 0; v < G.vex_num; v++ ){final[v] = 0; D[v] = G.arcs[v0][v].info;//最短路径为0 for ( w = 0; w < G.vex_num; w++ )path[v][w] = 0;if ( D[v] < INF ){ //存在v0到v到直达路径 path[v][v0] = 1;path[v][v] = 1;}}D[v0] = 0; final[v0] = 1;for ( i = 1; i < G.vex_num; ++i ){//其余G.vexnum-1个顶点 min = INF; for ( w = 0; w < G.vex_num; ++w )if ( !final[w] )// w顶点在v-s中 if ( D[w] < min ){//在v-s中找最短的距离 v = w;min = D[w];}final[v] = 1; for ( w = 0; w < G.vex_num; ++w ) if ( !final[w] && ( (min + G.arcs[v][w].info) < D[w]) ){//和原来的比较，取小着 D[w] = min + G.arcs[v][w].info; for ( t = 0; t < G.vex_num; t++ )path[w][t] = path[v][t];path[w][w] = 1;}}}
