c++ - Dijkstra算法中的优先级队列如何实现

Question

Dijkstra 算法使用优先级队列，该队列按距起点的距离排序，但顶点的距离在算法过程中会发生变化。我不确定优先队列何时重新排序，但如果我有以下比较器:

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

在算法中，我们只从队列中删除值，所以我无法想象它会完全重新排序。因此，如果距离值发生变化，队列将不会按距离顺序排列。

你如何实现与此类似的？

Answer 1

Google 最小-最大(通常是默认值)堆，它将作为优先队列工作。你总是在顶部弹出元素的地方。这将是距离最小的节点。