数据结构基础温故-5.图（下）：最短路径
图的最重要的应用之一就是在交通运输和通信网络中寻找最短路径。例如在交通网络中经常会遇到这样的问题：两地之间是否有公路可通；在有多条公路可通的情况下，哪一条路径是最短的等等。这就是带权图中求最短路径的问题，此时路径的长度不再是路径上边的数目总和，而是路径上的边所带权值的和。带权图分为无向带权图和有向带权图，但如果从A地到B地有一条公路，A地和B地的海拔高度不同，由于上坡和下坡的车速不同，那么边<A,B>和边<B,A>上表示行驶时间的权值也不同。考虑到交通网络中的这种有向性，本篇也只讨论有向带权图的最短路径。一般习惯将路径的开始顶点成为源点，路径的最后一个顶点成为终点。
一、单源点最短路径
单源点最短路径是指给定一个出发点（源点）和一个有向图，求出源点到其他各顶点之间的最短路径。对于下图左边所示的有向图G，设顶点0为源点，则其到其他各顶点的最短路径如下图右边所示。
从上图中可以看出，从源点0到终点4一共有4条路径：
（1）0→4 路径长度：90
（2）0→3→4 路径长度：90
（3）0→1→2→4 路径长度：70
（4）0→3→2→4 路径长度：60
可以看出，源点0到终点4的最短路径为第（4）条路径。为了求出最短路径，前人们已经做很多工作，为我们奉献了两个重要的算法：Dijkstra（迪杰斯特拉）和Floyd（弗洛伊德）算法，下面我们就来看看这两个算法。
二、Dijkstra算法
2.1 算法思想
Dijkstra在对最短路径的求解方式做了大量的观察之后，首先提出了按路径长度递增产生与顶点之间的路径最短的算法，以他的名字称之为Dijkstra算法。
Dijkstra算法的基本思想是：将图中顶点的集合分为两组S和U，并按最短路径长度的递增次序依次将集合U中的顶点加入到S中，在加入的过程中，总保持从原点v到S中各顶点的最短路径长度不大于从原点v到U中任何顶点的最短路径长度。
Dijkstra算法采用邻接矩阵存储图的信息并计算源点到图中其余顶点的最短路径，如下图所示。
2.2 算法实现
（1）代码实现
static void Dijkstra(int[,] cost, int v) { int n = cost.GetLength(1); // 计算顶点个数 int[] s = new int[n]; // 集合S int[] dist = new int[n]; // 结果集 int[] path = new int[n]; // 路径集 for (int i = 0; i < n; i++) { // 初始化结果集 dist[i] = cost[v, i]; // 初始化路径集 if (cost[v, i] > 0) { // 如果源点与顶点存在边 path[i] = v; } else { // 如果源点与顶点不存在边 path[i] = -1; } } s[v] = 1; // 将源点加入集合S path[v] = 0; for (int i = 0; i < n; i++) { int u = 0; // 指示剩余顶点在dist集合中的最小值的索引号 int minDis = int.MaxValue; // 指示剩余顶点在dist集合中的最小值大小 // 01.计算dist集合中的最小值 for (int j = 0; j < n; j++) { if (s[j] == 0 && dist[j] > 0 && dist[j] < minDis) { u = j; minDis = dist[j]; } } s[u] = 1; // 将抽出的顶点放入集合S中 // 02.计算源点经过顶点u到其余顶点的距离 for (int j = 0; j < n; j++) { // 如果顶点不在集合S中 if (s[j] == 0) { // 加入的顶点如与其余顶点存在边，并且重新计算的值小于原值 if (cost[u, j] > 0 && (dist[j] == 0 || dist[u] + cost[u, j] < dist[j])) { // 计算更小的值代替原值 dist[j] = dist[u] + cost[u, j]; path[j] = u; } } } } // 打印源点到各顶点的路径及距离 for (int i = 0; i < n; i++) { if (s[i] == 1) { Console.Write("从{0}到{1}的最短路径为：", v, i); Console.Write(v + "→"); // 使用递归获取指定顶点在路径上的前一顶点 GetPath(path, i, v); Console.Write(i + Environment.NewLine + "SUM:"); Console.WriteLine("路径长度为：{0}", dist[i]); } } } static void GetPath(int[] path, int i, int v) { int k = path[i]; if (k == v) { return; } GetPath(path, k, v); Console.Write(k + "→"); }
这里经历了三个步骤，第一步是构造集合U，第二步是寻找最短路径，第三步是重新计算替换原有路径。
（2）基本测试
这里要构造的有向带权图如下图所示：
static void DijkstraTest() { int[,] cost = new int[5, 5]; // 初始化邻接矩阵 cost[0, 1] = 10; cost[0, 3] = 30; cost[0, 4] = 90; cost[1, 2] = 50; cost[2, 4] = 10; cost[3, 2] = 20; cost[3, 4] = 60; // 使用Dijkstra算法计算最短路径 Dijkstra(cost, 0); }
运行结果如下图所示：
从图中可以看出，从源点0到终点4的最短路径为：0→3→2→4，该路径长度为60。
三、Floyd算法
3.1 算法思想
Floyd（弗洛伊德）算法提出了另外一种用于计算有向图中所有顶点间的最短路径，这种算法成为Floyd算法，它的形式较Dijkstra算法更为简单。
Floyd算法仍然使用邻接矩阵存储的图，同时定义了一个二维数组A，其中每一个分量A[i,j]是顶点i到顶点j的最短路径长度。另外还使用了另一个二维数组path来保存最短路径信息。Floyd算法的基本思想如下：
（1）初始时，对图中任意两个顶点Vi和Vj，如果从Vi到Vj存在边，则从Vi到Vj存在一条长度为cost[i,j]的路径，但该路径不一定是最短路径。初始化时，A[i,j]=cost[i,j]。
（2）在图中任意两个顶点Vi和Vj之间加入顶点Vk，如果Vi经Vk到达Vj的路径存在并更短，则用A[i,k]+A[k,j]的值代替原来的A[i,j]值。
（3）重复步骤（2），直到将所有顶点作为中间点依次加入集合中，并通过迭代公式不断修正A[i,j]的值，最终获得任意顶点的最短路径长度。
3.2 算法实现
（1）代码实现
static void Floyd(int[,] cost, int v) { int n = cost.GetLength(1); // 获取顶点个数 int[,] A = new int[n, n]; // 存放最短路径长度 int[,] path = new int[n, n];// 存放最短路径信息 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // 辅助数组A和path的初始化 A[i, j] = cost[i, j]; path[i, j] = -1; } } // Flyod算法核心代码部分 for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // 如果存在中间顶点K的路径 if (i != j && A[i, k] != 0 && A[k, j] != 0) { // 如果加入中间顶点k后的路径更短 if (A[i, j] == 0 || A[i, j] > A[i, k] + A[k, j]) { // 使用新路径代替原路径 A[i, j] = A[i, k] + A[k, j]; path[i, j] = k; } } } } } // 打印最短路径及路径长度 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (A[i, j] == 0) { if (i != j) { Console.WriteLine("从{0}到{1}没有路径!", i, j); } } else { Console.Write("从{0}到{1}的路径为：", i, j); Console.Write(i + "→"); // 使用递归获取指定顶点的路径 GetPath(path, i, j); Console.Write(j + " "); Console.WriteLine("路径长度为：{0}", A[i, j]); } } Console.WriteLine(); } } static void GetPath(int[,] path, int i, int j) { int k = path[i, j]; if (k == -1) { return; } GetPath(path, i, k); Console.Write(k + "→"); GetPath(path, k, j); }
（2）基本测试
static void FloydTest() { int[,] cost = new int[5, 5]; // 初始化邻接矩阵 cost[0, 1] = 10; cost[0, 3] = 30; cost[0, 4] = 90; cost[1, 2] = 50; cost[2, 4] = 10; cost[3, 2] = 20; cost[3, 4] = 60; // 使用Flyod算法计算最短路径 Floyd(cost, 0); }
运行结果如下图所示：
参考资料
（1）程杰，《大话数据结构》
（2）陈广，《数据结构（C#语言描述）》
（3）段恩泽，《数据结构（C#语言版）》
