之前我给大家分享过用迪杰斯特拉(Dijkstra)算法求图的最短路径(点我去看看)，今天我再给大家分享一个也是求图的最短路径的弗洛伊德(Floyd)算法

这两个算法都是求图的最短路径，有什么区别呢？
1、Dijkstra算法是求图中一个点到其他所有点的最短路径，Floyd算法是求图中任意两个顶点之间的最短路径
2、Dijkstra算法是通过贪婪算法来实现的，Floyd算法是通过动态规划算法实现的
3、Dijkstra算法的图，所有边的权重不能为负值，Floyd算法的图在不存在负值圈的前提下可以存在负的权重
4、Dijkstra算法在稀疏图上求最短路径更有效率，Floyd算法在稠密图上求最短路径更有效率
5、Dijkstra算法的代码实现比较复杂，Floyd算法的代码实现比较简单

讯享网

下面是一个图，有A到G七个顶点，顶点间连通用直线连接，直线上的数字代表两点间的权重，可以理解为路程、运输成本等概念，最短路径也就是权重和最小的路径：

下面的这个矩阵叫邻接矩阵，中间的数字是两个顶点的权重，也就是左边顶点到上面顶点的权重，就是左边顶点和上面顶点交叉的那个数字值。对角线全部为0，也就是顶点自己到自己的权重是0，INF代表无穷大，代表这两点之间不连通。这个邻接矩阵在接下来的代码中是以二维数组来实现的，INF则用Integer.MAX_VALUE来表示，也就是int的最大值：

下面是Floyd算法的Java代码实现，具体的算法精髓都在代码和其间的详细注释中。读者可以复制代码到IDE中运行，用DEBUG模式来研究算法的具体实现过程，最后控制台会输出示例图中任意两个顶点的最短路径信息：

/ * @author LiYang * @ClassName FloydAlgorithm * @Description Floyd(弗洛伊德)算法求最短路径 * @date 2019/10/25 10:46 */ public class FloydAlgorithm { 
    / * 用Floyd(弗洛伊德)算法求出所有顶点对的最短路径 * @param source 图的邻接矩阵 * @param distance Floyd(弗洛伊德)算法的距离表 * @param path Floyd(弗洛伊德)算法的路径表 */ public static void floydAlgorithm(int[][] source, int [][] distance, int[][] path){ 
    //矩阵的边长 int length = source.length; //初始化距离表和路径表 for (int i = 0; i < length; i++) { 
    for (int j = 0; j < length; j++) { 
    //复制矩阵图到距离表 distance[i][j] = source[i][j]; //初始化路径表 path[i][j] = j; } } //重要：运行Floyd(弗洛伊德)算法求所有顶点对的最短路径 for (int k = 0; k < length; k++) { 
    for (int i = 0; i < length; i++) { 
    for (int j = 0; j < length; j++) { 
    //如果当前中间顶点的距离小于之前的距离 //且中间顶点的两边距离不为无穷大(int最大值) if (distance[i][k] != Integer.MAX_VALUE && distance[k][j] != Integer.MAX_VALUE && distance[i][j] > distance[i][k] + distance[k][j]){ 
    //更新距离表 distance[i][j] = distance[i][k] + distance[k][j]; //更新路径表 path[i][j] = path[i][k]; } } } } } / * 将Floyd(弗洛伊德)算法的距离表和路径表，解析为任意两点间的最短路径距离和路径图 * @param distance Floyd(弗洛伊德)算法的距离表 * @param path Floyd(弗洛伊德)算法的路径表 * @param vertexName 顶点名字(以路径表中数字为下标取) */ public static void parseShortestPath(int[][] distance, int[][] path, String[] vertexName){ 
    for (int i = 0; i < path.length; i++) { 
    for (int j = 0; j < path.length; j++) { 
    //出发点和目的点不一样，才打印信息 //自己到自己，没有意义 if (i != j){ 
    //下一站的顶点 int next = path[i][j]; //记录路径，并加入出发点 StringBuffer route = new StringBuffer(vertexName[i]); //重要：只要未到达目的点 while (next != j){ 
    //加入当前顶点 route.append(" -> ").append(vertexName[next]); //更新下一站顶点 //重要：每次都是找path表的第j列，要么找到下一个顶点，要么找到目的顶点 next = path[next][j]; } //最后加入目的节点 route.append(" -> ").append(vertexName[j]); //输出两个顶点的最短距离，以及最短路径 System.out.println(String.format("%s到%s的最短距离为%d，最短路径：%s", vertexName[i], vertexName[j], distance[i][j], route.toString())); } } } } / * 获取示例图的邻接矩阵 * @return */ public static int[][] initGraphMatrix(){ 
    //无穷大距离 final int INF = Integer.MAX_VALUE; //生成示例图的邻接矩阵 int[][] matrix = new int[][]{ 
    { 
   0, 12, INF, INF, INF, 16, 14}, { 
   12, 0, 10, INF, INF, 7, INF}, { 
   INF, 10, 0, 3, 5, 6, INF}, { 
   INF, INF, 3, 0, 4, INF, INF}, { 
   INF, INF, 5, 4, 0, 2, 8}, { 
   16, 7, 6, INF, 2, 0, 9}, { 
   14, INF, INF, INF, 8, 9, 0} }; //返回图的邻接矩阵 return matrix; } / * 运行Floyd(弗洛伊德)算法求出所有顶点对的最短路径 * 提示：如果需要运行自己的图，则需要重新定义initGraphMatrix() * 方法里面的邻接矩阵，并重新定义顶点名数组String[] vertexName * @param args */ public static void main(String[] args) { 
    //生成示例图中的邻接矩阵(自定义邻接矩阵，改下面的方法的返回值) int[][] matrix = initGraphMatrix(); //Floyd(弗洛伊德)算法的距离表 int[][] distance = new int[matrix.length][matrix.length]; //Floyd(弗洛伊德)算法的路径表 int[][] path = new int[matrix.length][matrix.length]; //运行Floyd(弗洛伊德)算法 floydAlgorithm(matrix, distance, path); //邻接矩阵的下标对应的顶点名字(自定义邻接矩阵，改下面字符串数组) String[] vertexName = new String[]{ 
   "A", "B", "C", "D", "E", "F", "G"}; //根据距离表、路径表、名字数组，解析输出任意两点的最短距离和最短路径 parseShortestPath(distance, path, vertexName); } } 

运行上面代码的main方法，控制台将会输出示例图中的任意两顶点之间的最短路径详细信息：

讯享网A到B的最短距离为12，最短路径：A -> B A到C的最短距离为22，最短路径：A -> B -> C A到D的最短距离为22，最短路径：A -> F -> E -> D A到E的最短距离为18，最短路径：A -> F -> E A到F的最短距离为16，最短路径：A -> F A到G的最短距离为14，最短路径：A -> G B到A的最短距离为12，最短路径：B -> A B到C的最短距离为10，最短路径：B -> C B到D的最短距离为13，最短路径：B -> C -> D B到E的最短距离为9，最短路径：B -> F -> E B到F的最短距离为7，最短路径：B -> F B到G的最短距离为16，最短路径：B -> F -> G C到A的最短距离为22，最短路径：C -> B -> A C到B的最短距离为10，最短路径：C -> B C到D的最短距离为3，最短路径：C -> D C到E的最短距离为5，最短路径：C -> E C到F的最短距离为6，最短路径：C -> F C到G的最短距离为13，最短路径：C -> E -> G D到A的最短距离为22，最短路径：D -> E -> F -> A D到B的最短距离为13，最短路径：D -> C -> B D到C的最短距离为3，最短路径：D -> C D到E的最短距离为4，最短路径：D -> E D到F的最短距离为6，最短路径：D -> E -> F D到G的最短距离为12，最短路径：D -> E -> G E到A的最短距离为18，最短路径：E -> F -> A E到B的最短距离为9，最短路径：E -> F -> B E到C的最短距离为5，最短路径：E -> C E到D的最短距离为4，最短路径：E -> D E到F的最短距离为2，最短路径：E -> F E到G的最短距离为8，最短路径：E -> G F到A的最短距离为16，最短路径：F -> A F到B的最短距离为7，最短路径：F -> B F到C的最短距离为6，最短路径：F -> C F到D的最短距离为6，最短路径：F -> E -> D F到E的最短距离为2，最短路径：F -> E F到G的最短距离为9，最短路径：F -> G G到A的最短距离为14，最短路径：G -> A G到B的最短距离为16，最短路径：G -> F -> B G到C的最短距离为13，最短路径：G -> E -> C G到D的最短距离为12，最短路径：G -> E -> D G到E的最短距离为8，最短路径：G -> E G到F的最短距离为9，最短路径：G -> F