如果使用最大优先级队列，Dijkstra 算法如何工作？

Question

我最近在看 Dijkstra 算法的一些代码。该代码的目标是找到从顶点 1 到顶点 N 的最小成本路径。我在查看问题的解决方案时遇到了这个工作代码：

void dijkstra(int start, int n) {
    for(int i = 0; i<n; i++) {
        dist[i] = INF;
        pred[i] = -1;
    }
    dist[start] = 0;  
    priority_queue<ll> q;
    q.push(0);
    int u = 0;
    while(q.size()) {
        u = q.top();
        q.pop();
        for(int end : adj[u]) {
            ll w = weight.at(mp(u, end));
            if(dist[u] + w < dist[end]) {
                dist[end] = dist[u] + w;
                pred[end] = u;
                q.push(end);
            }
        } 
    }
}

此程序使用优先级队列来确定下一个要遍历的顶点（从顶点 1 开始）。但是，该算法中实现的优先级队列是标准的 C++ 优先级队列，即最大优先级队列。这意味着最大的元素具有最高的优先级。但是，我想到在Dijkstra的算法中，我们想先轮询最小的顶点？我不确定使用最大优先级队列如何适用于该算法。

Answer 1

你说的都对。不过要小心！ u是这个算法中邻居的索引。并且，如果具有更高索引的邻居之间的距离更小，它将正常工作。

此外，您应该注意到可以使用 std::greater<T>.

实现优先级队列，使得顶部元素将是最小值

如果使用最大优先级队列，Dijkstra 算法如何工作？

How does Dijkstra's Algorithm work if a max priority queue is used?

c++

algorithm

dijkstra

graph-algorithm