参考:大话数据结构
这是一个按照路径长度递增的次序产生最短路径的算法. 它并不是一次求出源点到目标点的最短路径, 而是一步步求出它们之间顶点的最短路径, 过程中都是基于已经求出的最短路径的基础上, 求得更远顶点的最短路径, 最终得到想要的结果.
- #define MAXVEX 9
- #define INFINITY
- typedef int PathMatrix[MAXVEX]
- typedef int ShortPathTable[MAXVEX]
- void ShortestPath_Dijkstra(MGraph G, int v0, PathMatrix *p, ShortPathTable *D)
- {
- int v,w,k,min;
- int final[MAXVEX]; //final[w]=1 表示求得顶点 v0 到 vw 的最短路径
- for(v=0;v<G.numVertexes;v++)
- {
- final[v] = 0; // 全部顶点初始化为未知最短路径状态
- (*D)[v] = G.matrix[v0][v]; // 将与 v0 点有连线的顶点加上权值
- (*p)[v] = 0; // 初始化路径数组 p 为 0
- }
- (*D)[v0] = 0; //v0 至 v0 路径为 0
- final[v0] = 1; //v0 至 v0 不需要求路径
- /* 开始主循环, 每次求得 v0 到某个 v 顶点的最短路径 */
- for(v=1;v<G.numVertexes;v++)
- {
- min = INFINITY;
- for(w=0;w<G.numVertexes;w++) // 寻找离 v0 最近的顶点
- {
- if(!final[w] && (*D)[w] < min)
- {
- k = w;
- min = (*D)[w];
- }
- }
- }
- final[k] = 1; // 将目前找到的最近的顶点置为 1
- for(w=0;w<G.numVertexes;w++)
- {
- if(!final[w] && (min + G.matrix[k][w])<(*D)[w]) // 如果警告 v 顶点的路径比现在这条路径的长度短的话
- {
- (*D)[w] = min + G.matrix[k][w];
- (*p)[w] = k;
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2601498.html