如何在Dijkstra算法中實現優先級隊列

Dijkstra算法使用一個優先級隊列，該隊列按照距離起始點的距離排序，但是算法中頂點的距離正在改變。我不知道做了優先級隊列重新排序本身時，但如果我有以下比較：如何在Dijkstra算法中實現優先級隊列

struct compareByDistance 
{ 
bool operator()(Vertex const &a, Vertex const &b) 
    { 
     return(getDistance(a) < getDistance(b)); 
    } 
};

在算法中我們只從隊列中刪除值，所以我無法想象，這將完全重新排序本身。因此，如果距離值發生變化，則隊列將不會按距離順序排列。

你如何以類似的方式實現它？

2013-03-07 gen

到目前爲止你寫了些什麼？這不是一個代碼寫入服務。 – Raedwald 2013-03-07 13:11:29

@Raedwald當然，這不是，我想知道一些指導方針，或者不是完整的書面代碼。維基百科說它應該用優先級隊列來完成，但我無法找到如何做到這一點。 – gen 2013-03-07 13:17:16

Google min-max（通常爲默認值）堆，它將作爲優先級隊列工作。你總是在頂部彈出元素。這將是距離最短的節點。

2013-03-07 13:16:40 Moddaman

一個可能的解決方案是有一個訪問數組，它跟蹤所有找到最小距離的節點（即它們已經從隊列中跳出一次）。每次將某個項目彈出隊列時，請檢查訪問陣列以查看節點的最短距離是否已找到。如果是，那就忽略那個元素。代碼如下所示： -

while(!queue.empty()) 
{ 
node n1= queue.top(); 
queue.pop(); 
if(visited[n1]) continue; 

//// 
//Rest of the code here 
//// 
}

注：這可能不是最優化的解決方案。

2013-05-11 05:56:57 avinash

回答