Dijkstra

一、算法过程

二、算法实现

#include <iostream> const int kNum = 100; // 最多顶点数量 const int kMax = INT32_MAX; // int32最大值 // 邻接矩阵 typedef struct Graph { char vertex[kNum]; // 顶点集合 int vertex_count; // 顶点数 int matrix[kNum][kNum]; // 邻接矩阵 }Graph; /* * Dijkstra最短路径。 * 即，统计图(G)中"顶点source"到其它各个顶点的最短路径。 * * 参数说明： * g -- 图 * source -- 起始顶点(start)。即计算"顶点source"到其它顶点的最短路径。 * previous -- 前驱顶点数组。即，previous[i]的值是"顶点source"到"顶点i"的最短路径所经历的全部顶点中，位于"顶点i"之前的那个顶点。 * distance -- 长度数组。即，distance[i]是"顶点source"到"顶点i"的最短路径的长度。 */ void Dijkstra(Graph g, int source, int *previous, int *distance) { int next; // 用于寻找最短路径中的下一个顶点 int min; // 路径最小值 int tmp; int flag[kNum]; // flag[i]=1表示"顶点source"到"顶点i"的最短路径已成功获取。 // 初始化 for (int i = 0; i < g.vertex_count; i++) { flag[i] = 0; // 顶点i的最短路径还没获取到。 previous[i] = 0; // 顶点i的前驱顶点为0。 distance[i] = g.matrix[source][i]; // 顶点i的最短路径为"顶点source"到"顶点i"的权。 } // 对"顶点source"自身进行初始化 flag[source] = 1; distance[source] = 0; // 遍历g.vertex_count-1次；每次找出一个顶点的最短路径。 for (int i = 1; i < g.vertex_count; i++) { // 寻找当前最小的路径； // 即，在未获取最短路径的顶点中，找到离顶点source最近的顶点(next)。 min = kMax; for (int j = 0; j < g.vertex_count; j++) { if (flag[j]==0 && distance[j]<min) { min = distance[j]; next = j; } } // 标记"顶点nearest"为已经获取到最短路径 flag[next] = 1; // 修正当前最短路径和前驱顶点 // 即，当已经"顶点顶点nearest的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。 for (int j = 0; j < g.vertex_count; j++) { tmp = (g.matrix[next][j]==kMax ? kMax : (min + g.matrix[next][j])); // 防止溢出 if (flag[j] == 0 && (tmp < distance[j]) ) { distance[j] = tmp; previous[j] = next; } } } // 打印dijkstra最短路径的结果 printf("从顶点(%c)到其它顶点的最短路径: \n", g.vertex[source]); for (int i = 0; i < g.vertex_count; i++) printf("\tshortest(%c, %c)=%d\n", g.vertex[source], g.vertex[i], distance[i]); } /* * // 邻接矩阵图 * A B C D E F G * * A 0 12 max max max max 14 * * B 12 0 10 max max 7 max * * C max 10 0 3 5 6 max * * D max max 3 0 4 max max * * E max max 5 4 0 2 8 * * F 16 7 6 max 2 0 9 * * G 14 max max max 8 9 0 * */ int main () { int previous[kNum]; int distance[kNum]; Dijkstra(Graph{ "ABCDEFG", 7, { {0, 12, kMax, kMax, kMax, kMax, 14}, {12, 0, 10, kMax, kMax, 7, kMax}, {kMax, 10, 0, 3, 5, 6, kMax}, {kMax, kMax, 3, 0, 4, kMax, kMax}, {kMax, kMax, 5, 4, 0, 2, 8 }, {16, 7, 6, kMax, 2, 0, 9 }, {16, 7, 6, kMax, 2, 0, 9 }} }, 3, previous, distance); return 0; }