Chapter 73

Home

Refactoring: Dijkstra with Priority Queue

The O(V) linear scan for the minimum-distance node is replaced by a priority queue. Push (distance, node) pairs, pop the smallest, and skip stale entries. O((V+E) log V) — the standard Dijkstra for all contests.

Before: O(V²) Linear Scan

C++ — O(V²)

// Find min unvisited — O(V) per iteration
int u = -1;
for (int i = 0; i < V; i++)
    if (!visited[i] && (u == -1 || dist[i] < dist[u])) u = i;

After: O((V+E) log V) with Priority Queue

C++ — Dijkstra with priority queue

vector dijkstra(vector>>& adj, int start) {
    int V = adj.size();
    vector dist(V, LLONG_MAX);
    priority_queue, vector>, greater<>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;  // stale entry — skip

        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

// V=10⁵, E=2×10⁵:  ~0.05 seconds

Rust — Dijkstra with BinaryHeap

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn dijkstra(adj: &[Vec<(usize, i32)>], start: usize) -> Vec {
    let v = adj.len();
    let mut dist = vec![i64::MAX; v];
    let mut pq = BinaryHeap::new();

    dist[start] = 0;
    pq.push(Reverse((0, start)));

    while let Some(Reverse((d, u))) = pq.pop() {
        if d != dist[u] { continue; }
        for &(v, w) in &adj[u] {
            let nd = d + w as i64;
            if nd < dist[v] {
                dist[v] = nd;
                pq.push(Reverse((nd, v)));
            }
        }
    }
    dist
}

💡 Skip stale entries

A node might be pushed into the PQ multiple times if its distance improves. The check if (d != dist[u]) continue skips outdated entries. Without it, you process the same node multiple times — correct but slow.

Key Takeaways