弗洛伊德 - Warshall算法邏輯 - 卡住

我試圖用這個邏輯來理解正在發生的事情與adjacency matrix，但我massivley困惑的地方說約interspacing是ABCD .....弗洛伊德 - Warshall算法邏輯 - 卡住

任何人都可以解釋這裏發生了什麼？

謝謝（標記爲Java作爲其這是在向我們展示的語言，所以如果有人發佈任何代碼示例，他們可以看到它是在語言）

http://compprog.wordpress.com/2007/11/15/all-sources-shortest-path-the-floyd-warshall-algorithm/

這裏是代碼：

for (k = 0; k < n; ++k) { 
    for (i = 0; i < n; ++i) 
     for (j = 0; j < n; ++j) 
      /* If i and j are different nodes and if 
       the paths between i and k and between 
       k and j exist, do */ 
      if ((dist[i][k] * dist[k][j] != 0) && (i != j)) 
       /* See if you can't get a shorter path 
        between i and j by interspacing 
        k somewhere along the current 
        path */ 
       if ((dist[i][k] + dist[k][j] < dist[i][j]) || 
         (dist[i][j] == 0)) 
        dist[i][j] = dist[i][k] + dist[k][j];

來源

2010-04-22 stan

@stan：Floyd-Warshall是典型的「DP算法」之一，以及Levenhstein的編輯距離和「0-1揹負」。要理解它，你需要了解什麼是「動態規劃」（大多數沒有CS學位的程序員都不瞭解DP）。關於這個主題的維基百科條目是很好的：http：//en.wikipedia.org/wiki/Dynamic_programming，否則你可以嘗試參加一些在線比賽（如TopCoder），其中通常很多問題需要DP解。 – SyntaxT3rr0r 2010-04-22 10:50:56

的弗洛伊德 - Warshall算法執行以下操作：

它着眼於è （k），然後在每個k中查找每個i, j，如果它可以通過從i到k然後從k到j首先進行更短的路徑。

所以看起來：

「我目前最短距離i到j路徑長度爲L0的，我目前最短距離i到k路徑長度爲L1的，我目前最短距離k到j路徑長度L2。

如果我結合當前最短路徑i to k和k to j到一條新路？這是新的路徑i to k to j比我目前的最短路徑0短？如果是這樣，它積累的長度L1和L2來計算新的最短路徑的長度。」

這意味着，k是從i到j的方式潛在的中途停留點。

來源

2010-04-22 09:07:50 phimuemue

Floyd-沃肖爾是dynamic programming問題

這幾乎是標準的（容易）把它寫在二維版本：

for (int k = 0; k < n; k++) 
    for (int i = 0; i < n; i++) 
     for (int j = 0; j < n; j++) 
      dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j])

但也許它可以幫助你用三維版本圖片，所以你可以看到所有的國家更明確：

for (int k = 0; k < n; k++) 
    for (int i = 0; i < n; i++) 
     for (int j = 0; j < n; j++) 
      dist[k][i][j] = min(dist[k-1][i][k] + dist[k-1][k][j], dist[k-1][i][j])

狀態的略深的解釋是在Algorithmist發現。

來源

2010-04-22 12:16:39 Larry

在你最後一行代碼中，應該有dist [k-1] [i] [j]而不是dist [i] [j]我認爲 – Karussell 2012-01-22 22:19:57

弗洛伊德 - Warshall算法邏輯 - 卡住

回答

相關問題