Floyd-Warshall算法最短路徑

我實現了Floyd-Warshall算法。根據他們的矩陣，我可以得到正確的結果，關於兩地之間的最短路徑和距離。我的問題是如何打印從i到j的最短距離。我做了一些研究，我發現了一個這樣的算法。任何人都可以解釋我該怎麼做，或者它是如何工作的，或者說任何其他建議？Floyd-Warshall算法最短路徑

PrintShortestPath(P,i,j){ 
    if(i==j) print i 
    else if (P[i][j]==NULL) 
     print "No path from i to j" 
    else{ 
     PrintShortestPath(P,i,P[i][j]) 
     print j 
    } 
}

來源

2012-06-11 bledi

弗洛伊德算法考慮了兩個節點之間的所有路徑，並保持最便宜的發現。你的代碼是遞歸地進行的。這裏是一個在C很好的解釋這個另一種實現方式： http://www.fearme.com/misc/alg/node88.html

您也可以考慮Dijkstra算法，這可能是稀疏圖更好的執行。

--L。

來源

2012-06-11 09:11:04 elomage

感謝的人，但我已經通過該算法計算了他們的所有距離。我不想打印單個路徑，而是打印讓我們說從x到y的路徑，我的意思是從x到y的路徑在它們內部有另一個路徑（x和y）。 – bledi

您發佈的算法中的矩陣P是前驅矩陣。它列出了每個路徑i - > j的前身。

這必須連同距離矩陣來計算：

P [I，J]被initalized爲NULL的forall I，J
在FW更新P的最內層循環[I，J]如果發現從節點k傳遞的較短路徑（使用P [k，j]）。

如果您發佈您的解決方案的距離，我可以更精確。

來源

2013-05-06 21:58:57 igon

Floyd-Warshall算法最短路徑

回答

相關問題