查找時間在Dijkstra算法基於堆優先級隊列

Question

我想用priority_queue作爲一個dikjstra算法頂點容器，呼籲extractMin後得到一個頂點u，我發現所有相鄰頂點v，然後我可能會叫decreaseKey爲v ，我知道decreaseKey花了O（lgN）時間，但在撥打decreaseKey之前，我必須先找到v的位置。

我用std::vector和std::make_heap/std::push_heap/std::pop_heap保持priority_queue，使用這種數據結構，以找到特定的數據將花費O（N）的時間，這將使得O（LGN）decreaseKey無意義。

那麼，dikjstra算法中頂點容器的常用方法是什麼，或者我應該在class Vertex中添加一個成員以保持它在堆中的位置？

Answer 1

首先你不需要使用std::***_heap函數; STL中已有priority_queue。

至於更新已經在堆中的值，您可以插入pair s的索引和距離。並保持距離矢量以驗證距離是否仍然有效或已更新;是這樣的：

typedef struct { 
    size_t index; /* index of vertex and the distance at which */ 
    int dist;  /* the vertex was pushed to the heap   */ 
} value_t; 

/* `a` has less priority than `b` if it is further away */ 
const auto comp = [](const value_t & a, const value_t & b){ 
    return b.dist < a.dist; 
}; 

priority_queue<value_t, vector<value_t>, decltype(comp)> heap(comp); 

/* the *most current* shortest distances for all nodes */ 
vector<int> dist(n, inf); 

然後Dikjstra循環將是這樣的：

while(!heap.empty()) { 
    const auto top = heap.top(); 
    heap.pop(); 

    if(dist[top.index] < top.dist) { 
      /* the node has already been added at a */ 
      /* shorter distance therefore skip it */ 
      continue; 
    } 
    /* process the node & its neighbors */ 
    /* push to the heap neighbors which get their `dist` deccreased */ 
} 

這是真的，有可能是在堆同一節點的多個副本（在不同的距離只有其中一個他們仍然有效）;但是您可能會發現堆的大小爲O(num. of edges)，因此堆仍然會執行O(log num. of nodes)。