小编Cho*_*Luo的帖子

有时在编程竞赛等过程中,我们需要一个简单的最小优先级队列的工作实现,使用reduce-key来实现Dijkstra算法等.我经常使用set <pair <key_value,ID >>和一个数组(映射ID - > key_value) )共同实现这一目标.

• 向集合添加元素需要O(log(N))时间.要从N个元素中构建优先级队列,我们​​只需将它们逐个添加到集合中.这总共需要O(N log(N))时间.

• 具有min key_value的元素只是集合的第一个元素.探测最小元素需要O(1)时间.删除它需要O(log(N))时间.

• 为了测试集合中是否有一些ID = k,我们首先在数组中查找其key_value = v_k,然后搜索集合中的元素(v_k,k).这需要O(log(N))时间.

• 要将某些ID = k的key_value从v_k更改为v_k',我们首先在数组中查找其key_value = v_k,然后搜索集合中的元素(v_k,k).接下来,我们从集合中删除该元素,然后将元素(v_k',k)插入集合中.然后我们也更新阵列.这需要O(log(N))时间.

虽然上述方法有效,但大多数教科书通常建议使用二进制堆来实现优先级队列,因为构建二进制堆的时间只是O(N).我听说在C++的STL中有一个使用二进制堆的内置优先级队列数据结构.但是,我不确定如何更新该数据结构的key_value.

在C++中使用最小优先级队列和密钥更新的最简单,最有效的方法是什么？

BFS,DFS和Dijkstra的实现几乎是一样的,除了BFS使用队列,DFS使用堆栈,而Dijkstra使用最小优先级队列？

更确切地说.我们是否可以对所有BFS,DFS和Dijkstra使用以下代码,Q是BFS的队列,DFS的堆栈和Dijkstra的最小优先级队列？谢谢!

Init d[]=Inf; // distance from the node s
Init c[]='w'; // color of nodes: 'w':undiscovered, 'g':discovered, 'b':fully explored
Init p[]=null; // previous node in the path
c[s]='g';
d[s]=0;
Q.push(s);
while(!Q.empty()) {
    u = Q.front();
    Q.pop();
    for v in adj[u] {
        if(c(v)=='w') {
            c[v]='g';
            if(d[u]+w(u,v)<d[v]) {
                d[v]=d[u]+w(u,v);
                p[v]=u;
            }
            Q.push(v);
        }
    }
    c[u]='b';
}