1. 介紹：

弗洛伊德算法和迪杰斯特拉算法一樣，都是求最短路徑的。迪杰斯特拉算法是求某一個(gè)頂點(diǎn)到其他各頂點(diǎn)的最短路徑，而弗洛伊德算法會(huì)求出各個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑。弗洛伊德算法更簡(jiǎn)單，但是時(shí)間復(fù)雜度相對(duì)較高。同樣以下圖為例：

假如有七個(gè)村莊(ABCDEFG)，有個(gè)人從G點(diǎn)出發(fā)，到其他六個(gè)村莊的最短路徑分別是多少？到A、B、F、E只有一條路，沒(méi)得選，但是到C有兩條路，可以是2 + 7，也可以是8 + 4，到D點(diǎn)可以是3 + 9，也可以是6 + 4。圖上標(biāo)明了距離我們當(dāng)然一看就知道怎么選，那么如何能讓程序選擇最短的路徑呢？

2. 算法思想：

• 設(shè)置頂點(diǎn)vi到vk的最短路徑為lik，頂點(diǎn)vk到vj的最短路徑為lkj，頂點(diǎn)vi到vj的路徑為lij。那么vi到vj的最短路徑為：min(lik + lkj, lij)。vk呢是圖中的任意一點(diǎn)，這樣就可以算出vi到vj的最短路徑了。

• 其他頂點(diǎn)之間的最短路徑用同樣的方式求得。

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}

• 然后還要用一個(gè)數(shù)組來(lái)初始化頂點(diǎn)的前驅(qū)關(guān)系，其實(shí)叫前驅(qū)關(guān)系可能不太好理解，可以理解為保存一條路徑的中間頂點(diǎn)。看了后面的例子就會(huì)明白。初始情況如下：

  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}

• 在第一輪循環(huán)中，以A頂點(diǎn)當(dāng)作中間頂點(diǎn)的所有情況進(jìn)行遍歷，然后更新上面的兩個(gè)二維數(shù)組。把A作為中間頂點(diǎn)到底是啥意思？看下面的路徑：

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

上面這3條路徑，A在中間，這個(gè)就叫做以A為中間頂點(diǎn)的情況。那么程序要如何找到這三條路徑呢？我們搞三個(gè)數(shù)組，一個(gè)表示中間頂點(diǎn)數(shù)組，一個(gè)表示出發(fā)頂點(diǎn)數(shù)組，一個(gè)表示終點(diǎn)數(shù)組，如下：

中間頂點(diǎn)：["A", "B", "C", "D", "E", "F", "G"]
出發(fā)頂點(diǎn)：["A", "B", "C", "D", "E", "F", "G"]
    終點(diǎn)：["A", "B", "C", "D", "E", "F", "G"]

然后三層for循環(huán)遍歷這個(gè)三個(gè)數(shù)組，看看以第一層循環(huán)中的頂點(diǎn)為中間頂點(diǎn)的路徑有多少條。

• 先看第一條以A為中間頂點(diǎn)的路徑，C到G的距離為9，原先C到G的距離是N，9小于N，所以更新該值，因?yàn)槭菬o(wú)向圖，所以G到C的距離也更新為9；同理更新C到B，B到C。但是G到B，B到G的距離不能更新，因?yàn)樵鹊?比現(xiàn)在的7更小。所以更新后的數(shù)組為：

  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作為中間頂點(diǎn)，所以，將前驅(qū)關(guān)系表中對(duì)應(yīng)位置的字母都更新成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. 代碼實(shí)現(xiàn)：

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; // 存放頂點(diǎn)
 int[][] edges; // 鄰接矩陣，存放邊，也是存放距離
 int[][] pre; // 前驅(qū)頂點(diǎn)
 
 /**
  * 構(gòu)造器
  * @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];
     }
    }
   }
  }
 }
 
 /**
  * 打印數(shù)組
  */
 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]));
  }
 }
}

這個(gè)代碼還是很好理解的，可能有小伙伴發(fā)現(xiàn)了，pre數(shù)組好像沒(méi)啥用，去掉了也可以求得最短路徑。沒(méi)錯(cuò)，是可以得到頂點(diǎn)到另一個(gè)頂點(diǎn)的最短路徑的值，但是不知道具體路徑是哪一條。pre數(shù)組就是用來(lái)記錄路徑的。