將節點引入優先級隊列（迭代器）

Question

我試圖用priority_queue（因爲我需要跟蹤距離源節點最近的節點）實現Dijkstra算法。

問題是：當探索一個節點時，它可能會發生，它被鏈接到尚未在優先級隊列中發現的另一個節點（即到優先級隊列的一個元素）。

似乎優先級隊列不支持迭代器，當我發現與它關聯的節點時，我怎麼可以將引用到優先級隊列元素？

Answer 1

std::priority_queue<T>既不支持迭代器也不支持接口來減少/增加節點的優先級：僅僅改變元素的優先級不會更新數據結構。你需要的是基於節點的版本std::priority_queue<T>。在Boost有這個目的的優先隊列。

雖然它不會讓複雜性完全正確，你可以使用爲std::priority_queue<T> Dijkstra算法：而不是存儲節點你會從訪問節點存儲邊緣與優先級爲目標的距離，可能未訪問節點節點使用給定的邊緣時。當彈出一個元素時，你需要檢查節點是否曾經訪問過。複雜度將是O(m log m)而不是，儘管（n是節點的數量而m是邊的數量）。