44-Floyd 算法

概述

Floyd算法是一个经典的动态规划算法，是解决任意两点间的最短路径(称为多源最短路径问题)的一种算法
也可以正确处理有向图或负权的最短路径问题
Dijkstra ~ Floyd
- Dijkstra算法
  - 单源最短路径，计算图中某一个顶点到其他顶点的最短路径
  - 选定一个顶点作为出发访问顶点，求出从出发访问顶点到其他顶点的最短路径
- Floyd算法
  - 多源最短路径，计算图中各个顶点之间的最短路径
  - 每一个顶点都是出发访问顶点，求出从每一个顶点到其他顶点的最短路径

算法思想

从任意顶点 i 到任意顶点 j 的最短路径不外乎 2 种可能：
- 直接从顶点 i 到顶点 j
- 从顶点 i 经过若干个顶点 k 到顶点 j
所以，我们假设 arcs(i, j) 为顶点 i 到顶点 j 的最短路径的距离，对于每一个顶点 k，我们检查 arcs(i, k) + arcs(k, j) < arcs(i, j) 是否成立
- 如果成立，证明从顶点 i 经顶点 k 再到顶点 j 的路径比顶点 i 直接到顶点 j 的路径短，我们便设置 arcs(i, j) = arcs(i, k) + arcs(k, j)
这样一来，当我们遍历完所有顶点 k，arcs(i, j) 中记录的便是顶点 i 到顶点 j 的最短路径的距离

算法分析

根据以往的经验，如果要让任意两个顶点（假设从顶点 a 到顶点 b ）之间的距离变得更短，唯一的选择就是引入第 3 个顶点（顶点 k），并通过顶点 k 中转（a → k → b）才可能缩短顶点 a 到顶点 b 之间的距离
这时问题便分解为：求取某一个顶点 k，使得经过中转顶点 k 后，使得两点之间的距离可能变短，且还可能需要中转两个或者多个顶点才能使两点之间的距离变短
于是，延伸到一般问题：
- 当不经过任意第 3 个顶点时，其最短路径为初始路径，即下图中的邻接矩阵所示
- 当只允许经过 1 号顶点时，求两点之间的最短路径该如何求呢？
  - 只需判断 arcs[i][1] + arcs[1][j] 是否比 arcs[i][j] 要小即可
  - arcs[i][j] 表示的是从 i 号顶点到 j 号顶点之间的距离
  - arcs[i][1] + arcs[1][j] 表示的是从 i 号顶点先到 1 号顶点，再从1号顶点到 j 号顶点的路程之和
举例
由于上述代码更新了两点之间经过 1 号顶点的最短距离 arcs[i][j]，因此，数组中每两个顶点之间对应距离都是最短的
此时 arcs[i][j] 的结果已经保存了中转 1 号顶点时的最短路径，如果再继续并入 2 号顶点为中转顶点，则是任意两个顶点都经过中转顶点 1 号顶点和 2 号顶点的最短路径
更一般的，继续并入下一个中转顶点一直到 vexCount 个时，arcs[i][j] 的结果保存的就是整个图中两点之间的最短路径了 // DP！

代码实现

public class FloydAlgorithm {
	public static void main(String[] args) {
		char[] vertexs = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		int[][] matrix = new int[vertexs.length][vertexs.length];
		final int N = 65535; // 表示不可以连接
		matrix[0] = new int[] { 0, 5, 7, N, N, N, 2 };
		matrix[1] = new int[] { 5, 0, N, 9, N, N, 3 };
		matrix[2] = new int[] { 7, N, 0, N, 8, N, N };
		matrix[3] = new int[] { N, 9, N, 0, N, 4, N };
		matrix[4] = new int[] { N, N, 8, N, 0, 5, 4 };
		matrix[5] = new int[] { N, N, N, 4, 5, 0, 6 };
		matrix[6] = new int[] { 2, 3, N, N, 4, 6, 0 };
		Graph graph = new Graph(vertexs, matrix);
		graph.show();
		graph.floyd();
		System.out.println();
		graph.show();
	}
}

class Graph {
	int vCount;
	char[] vertexs;
	int[][] dis; // 保存距离
	int[][] pre; // 保存前驱
	
	public Graph(char[] vertexs, int[][] dis) {
		super();
		vCount = vertexs.length;
		this.vertexs = vertexs;
		this.dis = dis;
		this.pre = new int[vCount][vCount];
		for(int i = 0; i < vCount; i++)
			for(int j = 0; j < vCount; j++)
				pre[i][j] = i;
	}
	
	public void floyd() {
		int len;
		for(int k = 0; k < vCount; k++) // k: 中间顶点
			for(int i = 0; i < vCount; i++) // i: 出发顶点
				for(int j = 0; j < vCount; j++) { // j: 终点
					len = dis[i][k] + dis[k][j];
					if(dis[i][j] > len) {
						dis[i][j] = len;
						pre[i][j] = k;
					}
				}
	}
	
	public void show() {
		System.out.print("  ");
		for(int i = 0; i < vCount; i++)
			System.out.printf("%8c  ", vertexs[i]);
		System.out.println();
		for(int i = 0; i < vCount; i++) {
			System.out.print(vertexs[i]+"  ");
			for(int j = 0; j < vCount; j++)
				System.out.printf("%c(%5d)  ", vertexs[pre[i][j]], dis[i][j]);
			System.out.println();
		}
	}
}