【原】弗洛伊德算法

貪挽懶月 2022-06-20 發(fā)布于廣東

展開全文

1. 介紹：

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

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

2. 算法思想：

設(shè)置頂點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}

然后還要用一個數(shù)組來初始化頂點的前驅(qū)關(guān)系，其實叫前驅(qū)關(guān)系可能不太好理解，可以理解為保存一條路徑的中間頂點?？戳撕竺娴睦泳蜁靼?。初始情況如下：

  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頂點當作中間頂點的所有情況進行遍歷，然后更新上面的兩個二維數(shù)組。把A作為中間頂點到底是啥意思？看下面的路徑：

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

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

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

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

先看第一條以A為中間頂點的路徑，C到G的距離為9，原先C到G的距離是N，9小于N，所以更新該值，因為是無向圖，所以G到C的距離也更新為9；同理更新C到B，B到C。但是G到B，B到G的距離不能更新，因為原先的3比現(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作為中間頂點，所以，將前驅(qū)關(guān)系表中對應(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. 代碼實現(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; // 存放頂點
 int[][] edges; // 鄰接矩陣，存放邊，也是存放距離
 int[][] pre; // 前驅(qū)頂點
 
 /**
  * 構(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]));
  }
 }
}