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

Question

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

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

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

您如何与此类似地实现它？

score 0 · Accepted Answer

Google min-max（通常为默认）堆，它将作为优先级队列工作。你总是在顶部弹出元素。这将是距离最小的节点。

score 0 · Accepted Answer

一种可能的解决方案是拥有一个访问过的数组，该数组跟踪已找到距离最小的所有节点（即它们已从队列中弹出一次）。每次从队列中弹出一个项目时，检查访问的数组以查看是否找到了节点的最短距离。如果是，则忽略该元素。代码看起来像： -

while(!queue.empty())
{
node n1= queue.top();
queue.pop();
if(visited[n1]) continue;

////
//Rest of the code here
////
}

注意：这可能不是最佳解决方案。

2 回答 2