Dijkstra的最短路徑算法如何與優先級隊列一起工作？

Question

我一直在閱讀在線網站，每個人都說使用優先級隊列會使它很好，但我不明白在這裏用作「優先級」的是什麼。

一開始，優先隊列上的第一項始終是起點節點嗎？如果是這樣，當我們用距離0提取起始節點時，我們如何從優先級隊列中獲取它的鄰居？

Answer 1

優先隊列Q存儲一組不同的元素。每個元素 x都有一個關聯的密鑰x.key

當Dijkstra基於優先級隊列。然後，我們將頂點存儲在與源的距離尚未確定的隊列中，並鍵入它們與源的當前距離。

看看這個pdf，其中算法是基於抽象數據結構稱爲優先級隊列，可以使用二進制堆實現。

http://www.cs.bris.ac.uk/~montanar/teaching/dsa/dijkstra-handout.pdf

Answer 2

當實現Dijkstra算法，您可以使用優先級隊列，以確定您的訪問節點的順序。

優先級隊列包含所有未訪問的節點，並允許您刪除（然後處理）具有最小指定距離的節點。

優先級隊列是非常重要的，因爲它確保節點永遠不會被訪問，直到其分配的距離是準確的，並且其已知的最短路徑實際上是最短路徑。這意味着你永遠不必訪問和處理任何節點兩次！

但是，請注意，Dijkstra算法可能在訪問之前多次減少節點的指定距離。這意味着優先隊列必須支持動態增加節點的優先級。 Java和C++提供的標準優先級隊列不支持這種操作，不能用於Dijkstra算法。相反，您應該使用ArrayList或std :: vector中的堆來實現自己的優先級隊列。