查找时间在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)。