Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说
弗洛伊德算法详解_弗洛伊德算法时间复杂度分析,希望能够帮助你!!!。

1.介绍

Floyd-Warshall算法（英语：Floyd-Warshall algorithm），中文亦称弗洛伊德算法或佛洛依德算法，是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题。

2.原理

弗洛伊德算法先定义了两个二维矩阵：

• 矩阵distance记录顶点间的最小路径 例如distance[2][1]= 12，说明顶点2 到 1 的最短路径为12；

• 矩阵pre记录顶点间最小路径中的前驱节点例如pre[2][1]= 0 说明，2 到 1的最短路径轨迹经过0，1的前驱节点为 0；

然后通过3重循环，middle为中转点，start为起点，end为终点，
循环比较distance[start][end] 和 distance[start][middle] +distance[middle][end] 最小值，如果distance[start][middle] + distance[middle][end] 为更小值，
则把distance[start][middle] + distance[middle][end] 赋值给distance[start][end]
以及设置 pre[start][end] = pre[middle][end]

tips : 输出具体路径的方法是从终点开始循环迭代起点那一行的pre数组的列下标，把列下标放进栈中，直到列下标等于起点。然后打印栈。例如打印distance[2][1]的路径，就循环迭代pre[2][1] 到 pre[2][2]，如下所示
pre[2][1] --> pre[2][0] --> pre[2][2] 那么2到1的路径就越是 2 --> 0 --> 1

pre[2][1] == 0 pre[2][0]==2 pre[2][2]=2

3.初始化图

class Graph { 
    //邻接矩阵 int[][] distance; //节点 char[] vertex; //节点数 int vertexNum; public Graph() { 
    //设一个最大值表示不可达到 int X = Integer.MAX_VALUE; //无向图的邻接矩阵 //用节点的下标表示节点,如 distance[0][1] 表示 A到B 的距离 this.distance = new int[][]{ 
    { 
   0, 5, 7, X, X, X, 2},// A { 
   5, 0, X, 9, X, X, 3},// B { 
   7, X, 0, X, 8, X, X},// C { 
   X, 9, X, 0, X, 4, X},// D { 
   X, X, 8, X, 0, 5, 4},// E { 
   X, X, X, 4, 5, 0, 6

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。