使用Floyd-Warshall尋找所有最短路徑和距離

首先，有一點背景：我正在構建一個帶有基本圖算法（Dijkstra，Floyd-Warshall，Bellman-Ford等）的簡單圖類作爲即將舉行的節目比賽參考表。使用Floyd-Warshall尋找所有最短路徑和距離

到目前爲止，我有弗洛伊德，沃肖爾的功能版本，但不足之處是，到目前爲止，它只是讓我在最短的距離值節點兩者之間，不是最短路徑。最好我希望在算法本身中進行路徑建立，而不必調用另一個函數來重建它。

下面是關於數據結構的一些信息，我使用的是：

vector< vector<int> > graph //contains the distance values from each node to each other node (graph[1][3] contains the length of the edge from node #1 to node #3, if no edge, the value is INF

vector< vector<int> > path //contains the "stepping stones" on how to reach a given node. path[st_node][end_node] contains the value of the next node on the way from end_node -> st_node

下面是我使用的示例圖表數據：

INF 10 INF INF INF INF 
INF INF 90 15 INF INF 
INF INF INF INF INF 20 
INF INF INF INF 20 INF 
INF INF 5 INF INF INF 
INF INF INF INF INF INF

和這裏的期望的值在「路徑」變量中（通過從每個節點運行Dijkstra獲得）：

INF 0 4 1 3 2 
INF INF 4 1 3 2 
INF INF INF INF INF 2 
INF INF 4 INF 3 2 
INF INF 4 INF INF 2 
INF INF INF INF INF INF

下面是我正在使用的算法代碼的鏈接：(via PasteBin)。

任何幫助將不勝感激！

編輯：我試圖Wikipedia's code生成路徑矩陣和這裏的結果：

INF INF 4 1 3 4 
INF INF 4 INF 3 4 
INF INF INF INF INF INF 
INF INF 4 INF INF 4 
INF INF INF INF INF 2 
INF INF INF INF INF INF

它有點工作，但是當涉及到代表「單」的步驟有問題。例如，從節點0到節點1的路徑無處不在。（但是，儘管如此，感謝Nali4Freedom的建議）

來源

2010-10-25 Mr. Llama

如果我正在閱讀這個權利，根據'graph'的第一行，只有一個來自節點＃0的邊，並且它導致節點＃1。所以'path'的第一行（或者第一列）應該是'Inf 1 1 1 1 1'。我錯過了什麼？ – Beta 2010-10-25 23:15:26

啊，我看你怎麼會覺得困惑。 'graph'中的每一行列出了從該節點離開的邊，而'path'中的每一行都包含了到達'node＃[row_num]'的路徑。例如，正確的「路徑」圖的第一行意味着要從節點5（col = 5）到達節點0（行= 0），返回路上的下一個節點是節點2.要到達節點0從節點2我們使用節點4，然後節點3，然後節點1，然後最終在我們的目的地與節點0. – 2010-10-26 05:07:40

Huzzah！

我在結果好辛苦盯從添加維基百科的代碼片段，我想出了一個適配器，它的成果轉化爲我的結果，而無需調用單獨的函數：

// Time to clean up the path graph... 
for (int st_node = 0; st_node < this->size; st_node++) 
{ 
    for (int end_node = 0; end_node < this->size; end_node++) 
    { 
     int mid_node = this->path[st_node][end_node]; 

     if (mid_node == INF) 
     { 
      // There is no mid_node, it's probably just a single step. 
      if (this->graph[st_node][end_node] != INF) 
      { 
       this->path[st_node][end_node] = st_node; 
      } 

     } else { 
      // The mid_node may be part of a multi-step, find where it leads. 
      while (this->path[mid_node][end_node] != INF) 
      { 
       if (this->path[mid_node][end_node] == mid_node) { break; } // Infinite loop 
       if (this->path[mid_node][end_node] == INF) { break; } // Dead end 

       mid_node = this->path[mid_node][end_node]; 
      } 

      this->path[st_node][end_node] = mid_node; 

     } // IF mid_node 
    } // FOR end_node 
} // FOR st_node

本質上講，這補償從節點A到節點B獲取單個步驟(mid_node == INF)時通過添加邊如果它存在於原始圖中。或者，如果它指向的節點只是到達目的節點(this->path[mid_node][end_node] != INF)的墊腳石，那麼它會挖掘直到找到它所通向的地方。

感謝您的幫助，猜猜我只是需要有人大聲思考！

來源

2010-10-25 22:39:06

維基百科有一些很好的信息和pseudocode。基本上你只需填寫| V | x | V | 'next'矩陣，其中元素i，j包含您需要從節點i到節點j獲取的頂點的索引。從i到j的最短路徑可以作爲從i到下一個[i] [j]和從下一個[i] [j]到j的路徑。你繼續像這樣遞歸地分解路徑，直到你有完整的路徑。

來源

2010-10-25 21:26:14

相信我，我給了它一個去，但我的設置的工作方式（默認值設置爲INF）它doesn工作不正常。：\ – 2010-10-25 21:40:00

使用Floyd-Warshall尋找所有最短路徑和距離

回答

相關問題