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

Question

I was recently looking at some code for Dijkstra's algorithm. The goal of the code was to find the minimum cost path from vertex 1 to vertex N. I came across this working code when looking at the solution to the problem:

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);
            }
        } 
    }
}

This program uses a priority queue in order to determine which vertices to traverse to next (starting from vertex 1). However, the priority queue implemented in this algorithm is the standard C++ Priority Queue which is a Max Priority Queue. This means that the largest elements have the highest priority. However, I thought that in Dijkstra's algorithm, we wanted to poll the smallest vertices first? I am unsure how using a Max Priority Queue works for this algorithm.

OmG OmG · Accepted Answer · 2020-04-25T20:21:05

Everything that you have mentioned is right. But, be careful! u is the index of neighbors in this algorithm. And, if neighbors with a higher index have a smaller distance, it will work correctly.

Moreover, you should notice that the priority queue can be implemented such that the top element will be the smallest value using std::greater<T>.

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

1 Answers