最短路徑算法

Question

我對加權圖上的最佳算法問題有疑問。給我一個帶有權重的邊界列表，一個帶有保存點的列表，一個starte和end-node以及一個步驟的最大距離。 輸出應該是一個保存點列表，可以從開始節點和結束節點一步訪問。

我想到了保存點列表中每個點的某種dijkstra算法。

我不確定這是個好主意，因爲如果我有很多保存點，我會多次計算很多路徑。歡迎每個想法/幫助！

非常感謝您提前！

Answer 1

你必須有一個條件，權重不能否定，否則問題變得非常棘手。否則，它只是一個廣度優先搜索，標記每個訪問節點的距離。所以你不重新訪問一個節點就是先前的移動以較低的成本訪問它。

您保留所有活動節點的優先級隊列，因此您每次都檢查成本最低的節點。優先級隊列實際上是正確的最難的部分。如果你檢查我的二進制圖像庫https://github.com/MalcolmMcLean/binaryimagelibrary的A *算法，你可以在那裏獲得優先級隊列。 *迷宮上的最短路徑非常相似，但您沒有啓發式，因爲您必須具有確切的最短路徑，而不是每個貼磚上有4/8條邊，您的節點具有任意數量的連接。