我對加權圖上的最佳算法問題有疑問。給我一個帶有權重的邊界列表,一個帶有保存點的列表,一個starte和end-node以及一個步驟的最大距離。 輸出應該是一個保存點列表,可以從開始節點和結束節點一步訪問。最短路徑算法
我想到了保存點列表中每個點的某種dijkstra算法。
我不確定這是個好主意,因爲如果我有很多保存點,我會多次計算很多路徑。歡迎每個想法/幫助!
非常感謝您提前!
我對加權圖上的最佳算法問題有疑問。給我一個帶有權重的邊界列表,一個帶有保存點的列表,一個starte和end-node以及一個步驟的最大距離。 輸出應該是一個保存點列表,可以從開始節點和結束節點一步訪問。最短路徑算法
我想到了保存點列表中每個點的某種dijkstra算法。
我不確定這是個好主意,因爲如果我有很多保存點,我會多次計算很多路徑。歡迎每個想法/幫助!
非常感謝您提前!
你必須有一個條件,權重不能否定,否則問題變得非常棘手。否則,它只是一個廣度優先搜索,標記每個訪問節點的距離。所以你不重新訪問一個節點就是先前的移動以較低的成本訪問它。
您保留所有活動節點的優先級隊列,因此您每次都檢查成本最低的節點。優先級隊列實際上是正確的最難的部分。如果你檢查我的二進制圖像庫https://github.com/MalcolmMcLean/binaryimagelibrary的A *算法,你可以在那裏獲得優先級隊列。 *迷宮上的最短路徑非常相似,但您沒有啓發式,因爲您必須具有確切的最短路徑,而不是每個貼磚上有4/8條邊,您的節點具有任意數量的連接。
謝謝,我可以看到相似之處!對不起,我沒有說,但重量都是正面的,使它更容易。 – Timmathstf
Do dijkstra從開始和結束節點。在遍歷圖時,要記住你看到的保存點,直到你到達總成本大於步長的節點。 –
哦,這聽起來好多了!非常感謝你! – Timmathstf