循環有向權重圖的2個給定節點之間的最短路徑

Question

如何獲得循環有向權重圖的2個給定節點之間的最短路徑作爲節點列表？

Answer 1

我覺得Dijkstra算法是你在找什麼：

• http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

要獲得的最短路徑，你必須使用一個額外的地圖（類型節點的節點列表 - > node）跟蹤你的節點的前輩。

假設，我們發現從A到C以上B.

開始與空地圖的最短路徑。當更新從節點A到節點B的暫定距離時，還可以將關係B - > A插入到映射中（這意味着A是B的前驅）。如果您發現到B的距離更短，則會覆蓋地圖條目。

當你的算法完成後，你的地圖包含B→A和C→B的條目。現在你可以通過地圖追蹤你的方式並創建一個列表。