Dijkstra(迪杰斯特拉)算法求单源最短路径问题
重要的事情说三遍：代码不是我写的！代码不是我写的！代码不是我写的！
第一个算法是严蔚敏数据结构（C语言版）上写的，第二个算法是王道数据结构上写的，我想着记录在博客上以后比较好找。
如有谬误或者不足还请批评指正！
void ShortestPath_DIJ(MGraph G, int v0, PathMatrix &P, ShortPathTable &D){//用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权长度D[v]//若P[v][w]为true，则w是从v0到v当前求得最短路径上的顶点//final[v]为true当且仅当v∈S，即已经求得从v0到v的最短路径for (v = 0; v < G.vexnum; ++v){final[v] = false;D[v] = G.arcs[v0][v];for (w = 0; w < G.vexnum; ++w)P[v][w] = false; //设空路径if (D[v] < INFINITY){P[v][v0] = true;P[v][v] = true;}}D[v0] = 0; //初始化，v0顶点属于S集final[v0] = true;//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集for (i = 1; i < G.vexnum; ++i) //其余G.vexnum-1个顶点{min = INFINITY; //当前所知离v0顶点的最近距离for (w = 0; w < G.vexnum; ++w) {if (!final[w]) //w顶点在V-S中if (D[w] < min) //w顶点离v0顶点更近{v = w;min = D[w];}}final[v] = true; //离v0顶点最近的v加入S集for (w = 0; w < G.vexnum; ++w) //更新当前最短路径及距离{if (!final[w] && (min + G.arcs[v][w] < D[w])) //修改D[w]和P[w]，w∈V-S{D[w] = min + G.arcs[v][w];P[w] = P[v];P[w][w] = true;}}}}
void Dijistra(Graph G, int v){int s[G.vexnum]; //记录已求得的最短路径的顶点int path[G.vexnum]; //path[i]表示从源点到顶点i之间的最短路径的前驱结点int dist[G.vexnum]; //记录从源点v到其他各顶点当前的最短路径长度for (int i = 0; i < G.vexnum; i++){dist[i] = G.edge[v][i]; //若从源点v到顶点i有弧，则dist[i]为弧上的权值，否则为∞s[i] = 0; //初始时集合s为空if (G.edge[v][i] < MAX) // 若从源点v到顶点i有弧path[i] = v; //则将源点v到顶点i的最短路径的前驱结点设为velsepath[i] = -1; //否则设为-1，表示没有前驱结点}s[v] = 1; //把源点v加入集合spath[v] = -1; //设置源点v的前驱结点为-1，源点v没有前驱结点//开始主循环，每次求得源点v到顶点i的最短路径，并把顶点i加入集合sfor (int i = 0; i < G.vexnum; i++) {int min = MAX; //记录当前所知离源点v的最近距离int u; //记录离源点v最近的顶点for (int j = 0; i < G.vexnum; j++){//若顶点j不属于集合s并且最短路径长度小于minif (s[j] == 0 && dist[j] < min){min = dist[j];u = j;}} //这个for循环作用是找到离源点v最近的顶点us[u] = 1; //将顶点u加入集合s//顶点u加入后，可能需要修改源点v到集合v-s中可达顶点当前的最短路径长度for (int j = 0; j < G.vexnum; j++){//若顶点j不属于集合s并且源点v->u->j的距离比源点v->j的距离更短if (s[j] == 0 && dist[u] + G.edge[u][j]; < dist[j]){dist[j] = dist[u] + G.edge[u][j]; //则修改源点v到j的当前最短路径长度path[j] = u; //源点v->u->j，修改顶点j的前驱结点为u}}}}
个人觉得第二个更好理解，因为path数组设置的更好。
输出源点v到顶点w的最短路径
void PrintPath(int path[], int w){InitStack(S); //利用辅助栈来实现逆序while (path[w] >= 0) //类似于并查集的Find操作{Push(S, w);w = path[w];} //path[源点]=-1退出循环Push(S, w); //把源点压入栈while (!StackEmpty(S)) //栈不空则循环{printf("%d ", Pop(S));}}
