弗洛伊德算法

1. 介绍：

弗洛伊德算法和迪杰斯特拉算法一样，都是求最短路径的。迪杰斯特拉算法是求某一个顶点到其他各顶点的最短路径，而弗洛伊德算法会求出各个顶点到其他顶点的最短路径。弗洛伊德算法更简单，但是时间复杂度相对较高。同样以下图为例：

最短路径问题

假如有七个村庄(ABCDEFG)，有个人从G点出发，到其他六个村庄的最短路径分别是多少？到A、B、F、E只有一条路，没得选，但是到C有两条路，可以是2 + 7，也可以是8 + 4，到D点可以是3 + 9，也可以是6 + 4。图上标明了距离我们当然一看就知道怎么选，那么如何能让程序选择最短的路径呢？

2. 算法思想：

• 设置顶点vi到vk的最短路径为lik，顶点vk到vj的最短路径为lkj，顶点vi到vj的路径为lij。那么vi到vj的最短路径为：min(lik + lkj, lij)。vk呢是图中的任意一点，这样就可以算出vi到vj的最短路径了。

• 其他顶点之间的最短路径用同样的方式求得。

3. 案例：

以上图为例，步骤如下：

• 初始化邻接矩阵，自己和自己用0表示，连不通的用N表示。如下：

  A  B  C  D  E  F  G
A{0, 5, 7, N, N, N, 2},
B{5, 0, N, 9, N, N, 3},
C{7, N, 0, N, 8, N, N},
D{N, 9, N, 0, N, 4, N},
E{N, N, 8, N, 0, 5, 4},
F{N, N, N, 4, 5, 0, 6},
G{2, 3, N, N, 4, 6, 0}

• 然后还要用一个数组来初始化顶点的前驱关系，其实叫前驱关系可能不太好理解，可以理解为保存一条路径的中间顶点。看了后面的例子就会明白。初始情况如下：

  A  B  C  D  E  F  G
A{A, A, A ,A, A, A, A},
B{B, B, B ,B, B, B, B},
C{C, C, C, C, C, C, C},
D{D, D, D, D, D, D, D},
E{E, E, E, E, E, E, E},
F{F, F, F, F, F, F, F},
G{G, G, G, G, G, G, G}

• 在第一轮循环中，以A顶点当作中间顶点的所有情况进行遍历，然后更新上面的两个二维数组。把A作为中间顶点到底是啥意思？看下面的路径：

C --> A --> G：9
C --> A --> B：12
G --> A --> B：7

上面这3条路径，A在中间，这个就叫做以A为中间顶点的情况。那么程序要如何找到这三条路径呢？我们搞三个数组，一个表示中间顶点数组，一个表示出发顶点数组，一个表示终点数组，如下：

中间顶点：["A", "B", "C", "D", "E", "F", "G"]
出发顶点：["A", "B", "C", "D", "E", "F", "G"]
    终点：["A", "B", "C", "D", "E", "F", "G"]

然后三层for循环遍历这个三个数组，看看以第一层循环中的顶点为中间顶点的路径有多少条。

• 先看第一条以A为中间顶点的路径，C到G的距离为9，原先C到G的距离是N，9小于N，所以更新该值，因为是无向图，所以G到C的距离也更新为9；同理更新C到B，B到C。但是G到B，B到G的距离不能更新，因为原先的3比现在的7更小。所以更新后的数组为：

  A   B   C   D   E   F   G
A{0,  5,  7,  N,  N,  N,  2},
B{5,  0,  12, 9,  N,  N,  3},
C{7, 12,  0,  N,  8,  N,  9},
D{N,  9,  N,  0,  N,  4,  N},
E{N,  N,  8,  N,  0,  5,  4},
F{N,  N,  N,  4,  5,  0,  6},
G{2,  3,  9,  N,  4,  6,  0}

上面更新了距离的地方，都用到了A作为中间顶点，所以，将前驱关系表中对应位置的字母都更新成A，所以就变成了：

  A  B  C  D  E  F  G
A{A, A, A ,A, A, A, A},
B{B, B, A ,B, B, B, B},
C{C, A, C, C, C, C, A},
D{D, D, D, D, D, D, D},
E{E, E, E, E, E, E, E},
F{F, F, F, F, F, F, F},
G{G, G, A, G, G, G, G}

3. 代码实现：

public class FloydDemo {
 
 private static final int N = 999;
 
 public static void main(String[] args) {
  String[] vertexs = {"A", "B", "C", "D", "E", "F", "G"};
  int[][] edges = {
   {0, 5, 7 ,N, N, N, 2},
   {5, 0, N ,9, N, N, 3},
   {7, N, 0 ,N, 8, N, N},
   {N, 9, N ,0, N, 4, N},
   {N, N, 8 ,N, 0, 5, 4},
   {N, N, N ,4, 5, 0, 6},
   {2, 3, N ,N, 4, 6, 0}
  };
  Graph graph = new Graph(vertexs, edges);
  graph.floyd();
  graph.printArr();
 }

}

class Graph{
 String[] vertexs; // 存放顶点
 int[][] edges; // 邻接矩阵，存放边，也是存放距离
 int[][] pre; // 前驱顶点
 
 /**
  * 构造器
  * @param vertexs
  * @param edges
  */
 public Graph(String[] vertexs, int[][] edges) {
  this.vertexs = vertexs;
  this.edges = edges;
  this.pre = new int[vertexs.length][vertexs.length];
  for (int i=0; i<vertexs.length; i++) {
   Arrays.fill(pre[i], i);
  }
 }
 
 /**
  * 
  */
 public void floyd() {
  int len = 0;
  for (int k=0; k<vertexs.length; k++) {
   for (int i=0; i<vertexs.length; i++) {
    for (int j=0; j<vertexs.length; j++) {
     len = edges[i][k] + edges[k][j];
     if (len < edges[i][j]) {
      edges[i][j] = len;
      pre[i][j] = pre[k][j];
     }
    }
   }
  }
 }
 
 /**
  * 打印数组
  */
 public void printArr() {
  System.out.println("distance: ");
  for (int i=0; i<edges.length; i++) {
   System.out.println(Arrays.toString(edges[i]));
  }
  
  System.out.println("pre: ");
  for (int i=0; i<pre.length; i++) {
   System.out.println(Arrays.toString(pre[i]));
  }
 }
}

这个代码还是很好理解的，可能有小伙伴发现了，pre数组好像没啥用，去掉了也可以求得最短路径。没错，是可以得到顶点到另一个顶点的最短路径的值，但是不知道具体路径是哪一条。pre数组就是用来记录路径的。

扫描二维码