void ShortestPath_DIJAMGraph G int v0 0为图中源点下标 n = Gvexnum; 图G中的顶点个数n个顶点的初始化 forv=0; vn; ++v Sv=false; 从下标为v0的源点到下标为v的顶点这两点的最短路径没有被确定 Dv=Garcsv0v; 从下标为v0的源点到下标为v的顶点这两点的当前最短路径长度 ifDv MaxInt 如果下标为v

#include <stdio.h> #define MaxInt 999999 #define MAXVEX 100

typedef struct{ int arcs[MAXVEX][MAXVEX]; //邻接矩阵 int vexnum; //顶点个数 int arcnum; //弧的个数 }AMGraph;

void ShortestPath_DIJ(AMGraph G, int v0){ int n = G.vexnum; //图G中的顶点个数 int v, i, w; int min, v; int S[MAXVEX]; //集合S，用于存放已确定最短路径的顶点 int D[MAXVEX]; //用于存放源点到各顶点的最短路径长度 int Path[MAXVEX]; //用于存放最短路径的前驱顶点 //n个顶点的初始化 for(v=0; v<n; ++v){ S[v]=0; //从下标为v0的源点到下标为v的顶点，这两点的最短路径没有被确定 D[v]=G.arcs[v0][v]; //从下标为v0的源点到下标为v的顶点,这两点的当前最短路径长度 if(D[v] < MaxInt) //如果下标为v0的源点到下标为v的顶点之间有弧，则将下标为v的顶点的前驱置为v0 Path[v]=v0; //初始化时，下标为v的顶点的直接前驱顶点的下标为v0 else //如果下标为v0的源点到下标为v的顶点之间没有弧，则将下标为v的顶点的前驱置为-1 Path[v]=-1; //初始化时，下标为v的顶点无直接前驱 } //上面初始化时将其设置为了false，这里重新设置 S[v0]=1; //将下标为v0的源点加入集合S. //上面初始化时将其设置为了 ∞，这里重新设置 D[v0]=0; //源点到源点的最短路径为0. //初始化结束 //开始主循环，每次求得源点v0到某个顶点v的最短路径，将v加到集合S for(i=1; i<n; ++i){ //对除过源点的其余n-1个顶点，依次进行计算 min=MaxInt; //MaxInt等价于邻接矩阵中的 ∞ for(w=0; w<n; ++w) if(!S[w] && D[w]<min){ //选择一条当前的最短路径，终点为v v = w; min=D[w]; } S[v]=1; //将下标为v的顶点加入集合S,表示已经求出源点到下标为v的顶点之间的最短路径 for(w=0; w<n; ++w) //更新从源点出发到集合V-S中所有顶点的最短路径长度 if( !S[w] && (D[v]+G.arcs[v][w]<D[w]) ){ D[w]=D[v]+G.arcs[v][w]; //更新D[w] Path[w]=v; //更改w的前驱为v } } //打印最短路径和最短路径长度 for(i=0; i<n; ++i){ printf("v%d -> v%d: ", v0, i); if(D[i] == MaxInt){ printf("No path\n"); } else{ printf("%d", v0); int j = i; while(Path[j] != v0){ printf(" -> %d", Path[j]); j = Path[j]; } printf(" -> %d\n", i); } printf("Shortest path length: %d\n", D[i]); } }

int main(){ AMGraph G; G.vexnum = 4; G.arcnum = 6; int i, j; for(i=0; i<G.vexnum; ++i){ for(j=0; j<G.vexnum; ++j){ G.arcs[i][j] = MaxInt; } } G.arcs[0][1] = 1; G.arcs[0][2] = 5; G.arcs[1][0] = 1; G.arcs[1][2] = 3; G.arcs[1][3] = 7; G.arcs[2][0] = 5; G.arcs[2][1] = 3; G.arcs[2][3] = 2; G.arcs[3][1] = 7; G.arcs[3][2] = 2; ShortestPath_DIJ(G, 0); return 0;