Dijkstra算法使用一個優先級隊列,該隊列按照距離起始點的距離排序,但是算法中頂點的距離正在改變。我不知道做了優先級隊列重新排序本身時,但如果我有以下比較:如何在Dijkstra算法中實現優先級隊列
struct compareByDistance
{
bool operator()(Vertex const &a, Vertex const &b)
{
return(getDistance(a) < getDistance(b));
}
};
在算法中我們只從隊列中刪除值,所以我無法想象,這將完全重新排序本身。因此,如果距離值發生變化,則隊列將不會按距離順序排列。
你如何以類似的方式實現它?
到目前爲止你寫了些什麼?這不是一個代碼寫入服務。 – Raedwald 2013-03-07 13:11:29
@Raedwald當然,這不是,我想知道一些指導方針,或者不是完整的書面代碼。維基百科說它應該用優先級隊列來完成,但我無法找到如何做到這一點。 – gen 2013-03-07 13:17:16