圖最短路徑無限循環

enter image description here 圖最短路徑無限循環

所以我的油漆技能不是最好的，但我認爲它顯示了很好的例子。想象一下，我想計算A和C之間的最短路徑，考慮到我發現的所有算法都是貪婪的，難道它會陷入A和B之間的無限循環？

任何消耗？

在此先感謝

來源

2015-06-20 Carlos Pereira

不，不應該有一個無限循環。

圖中的訪問節點和未訪問節點將保持跟蹤狀態，並且訪問節點將永遠不會再次訪問。

在您的例子：

標記所有節點爲未訪問，除了這是訪問
與一開始的起始節點，請訪問B，作爲訪問標記B
B只能訪問或作爲訪問C，但A已經被標記
唯一可用的節點是C，這是未訪問過

來源

2015-06-20 14:58:19 rob

如果您嘗試獲取所有最短路徑的列表，請確保您將每個節點的進程重複爲起始節點。 – jdweng

@rob噢，確實很有道理！謝謝。所以我可以在這裏使用Dijkstra，對吧？ –

是的，你可以在這裏使用Dijkstra算法。 – rob

我通常把INT o每個節點從起點開始的距離和路徑（節點列表）。當我輸入一個節點時，我將當前距離與現有距離進行比較。如果當前距離比現有距離短，我用舊路徑替換新路徑。

另一種方法是保存每個節點到每個其他節點的距離列表。在離開每個節點時填寫此列表。

從A開始：設置A已經訪問過。轉到B.然後回到A. A已經被訪問過，所以在B添加到B到A的距離爲26. 從B移動到D.然後返回到B. B已經訪問過，所以在D添加距離D到B爲96 。從D到A的距離爲96 + 26 = 112. 從D移動到E.然後返回D. D已經訪問過，所以在E加上距離E到D爲21.添加從E到B的距離爲21 + 96 = 117.將距離E添加到A，作爲21 + 96 + 26 = 143。

來源

2015-06-22 20:16:08 jdweng

圖最短路徑無限循環

回答

相關問題