使用Dijkstra和最小堆找到節點之間的最短路徑C++

Question

這是更常見的問題。我有一張地圖將城市名稱映射到其節點（包含基本信息，如國家，經緯度，長等）。每個城市節點都有一組指向目標節點的邊。邊緣有時間和成本。我想找到在兩個節點之間旅行的最短時間，但我已經開始迷惑自己瞭解這個最好的方法。

我已經創建了我自己的基於城市節點向量的最小堆類。我能夠創建地圖，從地圖添加城市節點到最小堆。我寫了dijkstra的算法來找到最短路徑，它適用於一些路徑，但不是全部。我相信這是因爲當我更新dijkstra算法的城市節點的權重時，堆未被正確排序。

一旦我更新了一個節點的權重，我該如何重新堆積堆以便最低的權重位於頂部？

謝謝！

Answer 1

如果你想整個堆，然後進行排序有一個快速瀏覽一下 http://en.wikipedia.org/wiki/Heapsort

有上有一些僞助陣，你可能需要重新安排它來獲得頂部的最低，但應工作爲你而出。否則，你可以看看堆堆冒泡，並在每個階段應用它，而不是完全重新組織堆。

http://en.wikipedia.org/wiki/Binary_heap

他們有點複雜來形容這裏，但向上/向下堆冒泡將確保您的堆正確組織。值得注意的是，在最壞的情況下，堆排序將在O（n log n）上運行，而大多數操作的冒泡爲O（log n）。