Dijkstra’s algorithm

Find shortest paths when every edge weight is nonnegative. A priority queue always selects the smallest tentative distance.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. Set the source distance to 0 and all others to infinity.
2. Pop the lowest distance and skip outdated queue entries.
3. Relax each outgoing edge: replace a worse distance with a better one.
4. Nonnegative edges ensure the smallest current distance cannot later improve through a longer route.
5. The heap may contain obsolete entries, so dv!=d[v] skips stale distances. long long keeps path sums safe under the stated bounds.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
vector<long long>dijkstra(const vector<vector<pair<int,int>>>&g,int s){
    const long long INF=(1LL<<62);
    vector<long long>d(g.size(),INF);
    using P=pair<long long,int>;
    priority_queue<P,vector<P>,greater<P>>pq;
    d[s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        auto[dv,v]=pq.top();
        pq.pop();
        if(dv!=d[v]){
            continue; // Stale entry.
        }
        for(auto[u,w]:g[v]){
            if(d[u]>dv+w){
                d[u]=dv+w;
                pq.push({d[u],u});
            }
        }
    }
    return d;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,source;
    cin>>n>>m>>source;
    vector<vector<pair<int,int>>>graph(n+1);
    for(int i=0;i<m;i++){
        int a,b,weight;
        cin>>a>>b>>weight;
        graph[a].push_back({b,weight});
    }
    vector<long long>distance=dijkstra(graph,source);
    for(int vertex=1;vertex<=n;vertex++){
        if(vertex>1){
            cout<<' ';
        }
        if(distance[vertex]==(1LL<<62)){
            cout<<"INF";
        }
        else{
            cout<<distance[vertex];
        }
    }
    cout<<'\n';
}

Complexity analysis

O((V + E) log(V + E)) with lazy heap entries; O(V + E) space.

Example input and output

Read n m source, then m directed edges a b weight. Require 1≤n≤200000 and 0≤weight≤10^9. Print distances from source to labels 1..n, using INF for unreachable vertices.

Input

4 4 1
1 2 5
1 3 1
3 2 1
2 4 2

Output

0 2 1 4

The cheaper route to 2 is 1→3→2 with cost 2. Continuing to 4 gives cost 4.

Practical applications

Use Dijkstra for nonnegative weighted routes. Use Bellman–Ford when negative weights are possible.

Check your understanding

Which edge weights are allowed?

Put it into practice

Find the cheapest route in an undirected weighted road network.