Dijkstra's algorithm

Deep dive

How it works

In: directed graph with non-negative edge weights (CSR), a source, optionally a target · Out: distance and parent per vertex (all vertices, or those settled before the target) · State: none between calls; per call dist, parent and a heap · Cost: O((V + E) log V) with a binary heap

1. dist[s] = 0, every other dist = ∞. Heap = {(0, s)}.
2. Pop the minimum (d, u). If d > dist[u], the entry is stale: skip it.
3. If u is the target, stop. dist[u] is final once u is popped, not when it is pushed.
4. For each edge (u, v, w): if d + w < dist[v], set dist[v] = d + w and parent[v] = u, and push (d + w, v).
5. Follow parent back from the target for the path.

settled ◉──────────────► frontier (in heap) ──► unseen
         every settled d ≤ every frontier d (needs w ≥ 0)

Code

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

pub struct Graph { off: Vec<u32>, to: Vec<u32>, w: Vec<u32> } // CSR with weights

impl Graph {
    pub fn from_edges(n: usize, edges: &[(u32, u32, u32)]) -> Graph {
        let mut off = vec![0u32; n + 1];
        for &(u, _, _) in edges { off[u as usize + 1] += 1; }
        for i in 0..n { off[i + 1] += off[i]; }
        let (mut pos, mut to, mut w) = (off.clone(), vec![0; edges.len()], vec![0; edges.len()]);
        for &(u, v, c) in edges {
            let p = pos[u as usize] as usize;
            to[p] = v;
            w[p] = c;
            pos[u as usize] += 1;
        }
        Graph { off, to, w }
    }
}

/// Returns (dist, parent). With Some(target) it stops early; other distances are then upper bounds.
pub fn dijkstra(g: &Graph, s: u32, target: Option<u32>) -> (Vec<u64>, Vec<u32>) {
    let n = g.off.len() - 1;
    let mut dist = vec![u64::MAX; n];
    let mut parent = vec![u32::MAX; n];
    let mut heap = BinaryHeap::new();
    dist[s as usize] = 0;
    heap.push(Reverse((0u64, s)));
    while let Some(Reverse((d, u))) = heap.pop() {
        if d > dist[u as usize] { continue; } // stale duplicate (lazy deletion)
        if Some(u) == target { break; } // settled: final
        for e in g.off[u as usize] as usize..g.off[u as usize + 1] as usize {
            let (v, nd) = (g.to[e] as usize, d + g.w[e] as u64);
            if nd < dist[v] {
                dist[v] = nd;
                parent[v] = u;
                heap.push(Reverse((nd, v as u32)));
            }
        }
    }
    (dist, parent)
}

pub fn path(parent: &[u32], s: u32, t: u32) -> Option<Vec<u32>> {
    let (mut p, mut v) = (vec![t], t);
    while v != s {
        v = parent[v as usize];
        if v == u32::MAX { return None; } // unreachable
        p.push(v);
    }
    p.reverse();
    Some(p)
}

Complexity and constants

• Heap operations: up to E pushes and pops with lazy deletion, each O(log E). The heap entry is 16 B here; pack (dist << 32 | vertex) into one u64 when distances fit in 32 bits.
• Constant factors: each pop is about log₂(heap) levels of sift-down. A 4-ary heap halves the depth and keeps the children in one cache line, often 1.2-2× faster than BinaryHeap.
• Road graphs: about 2.5 edges per vertex, so heap work dominates. Social graphs: the edge scans dominate.
• Bidirectional Dijkstra: stop when top_fwd + top_bwd ≥ best path found. It searches about two balls of radius d/2 instead of one of radius d.

Efficiency

• Cost: measured with the code above on an Apple M4 Pro, one thread, random graph with 2^20 vertices and 4 · 2^20 edges, weights 1-100, best of 3: full single-source run 311 ms (74 ns per edge); stopping at a random target 144 ms on average. Memory: graph 8 B per edge plus 4 B per vertex, dist and parent 12 B per vertex. Bound: heap sifting and cache misses on dist[v].
• Levers:
  • pack (dist, vertex) into one u64 and keep u32 distances — 2.1× (147 ms, identical distances; measured) — distances below 2^32
  • stop when the target is popped — 2.2× on random targets (measured) — point-to-point queries
  • 4-ary heap — 1.2-2× over BinaryHeap (Complexity and constants, not measured here) — heap-bound runs
  • bidirectional search — about half as many settled vertices (Key facts) — point-to-point queries
  • preprocessing (Contraction Hierarchies) — well under a millisecond per query against seconds on continental road networks (Key facts; Geisberger et al. 2008) — static road graphs with many queries
• Naive → standard → state of the art:
  • scan all vertices for the minimum · O(V²) (Dijkstra 1959)
  • binary heap with lazy deletion (code above) · 311 ms on the graph above
  • packed heap entries · 147 ms; Contraction Hierarchies for repeated queries · sub-millisecond per query on road networks

Implementation notes

• Integer weights: a bucket queue (Dial) is O(E + V·C) for max weight C, and a radix heap is O(E + V log C). Both beat comparison heaps when C is small.
• Many queries: don't reallocate dist per query. Keep a list of touched vertices and reset only those, or use a generation counter per entry.
• Floats: f64 is not Ord. Use total_cmp, or store weights as fixed-point integers (also avoids ties from rounding).
• Parallel: Δ-stepping buckets distances into width Δ and relaxes each bucket in parallel. It is the standard parallel SSSP on GPUs and multicores.
• Turn costs and restrictions (roads): run on the edge-based graph (states = edges), not on intersections.
• Path storage: parent per vertex is enough; for multiple targets, reconstruct paths lazily.

Pitfalls

• A negative edge silently gives wrong answers: a vertex may be finalized before a cheaper path through a negative edge is found.
• Stopping when the target is pushed instead of popped returns non-shortest paths.
• Forgetting the stale-entry check: the heap still works, but each stale pop rescans edges, with worst case O(E · deg).
• u32 distance overflow on long weighted paths. Use u64 sums.
• Time-dependent travel times (traffic, timetables): Dijkstra stays correct only under the FIFO property, meaning that leaving later never gets you there earlier.

Variants and alternatives

In production

Networking: OSPF and IS-IS routers run it for their shortest-path trees (RFC 2328, RFC 1195). Maps: OSRM (Contraction Hierarchies and MLD; Luxen, Vetter 2011), GraphHopper, Valhalla, pgRouting. Games: distance fields (Dijkstra maps). Image editing: Intelligent Scissors (Mortensen, Barrett 1995). Libraries: Boost Graph Library, NetworkX.

Implementations

Sources

• E. W. Dijkstra, A Note on Two Problems in Connexion with Graphs, Numerische Mathematik, 1959. paper
• M. Fredman, R. Tarjan, Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms, JACM, 1987. paper
• M. Chen et al., Priority Queues and Dijkstra's Algorithm, UT Austin technical report TR-07-54, 2007.
• R. Geisberger, P. Sanders, D. Schultes, D. Delling, Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks, WEA, 2008. paper
• U. Meyer, P. Sanders, Δ-stepping: A Parallelizable Shortest Path Algorithm, Journal of Algorithms, 2003. paper
• H. Bast et al., Route Planning in Transportation Networks, in Algorithm Engineering (LNCS 9220), 2016. paper
• D. Luxen, C. Vetter, Real-time Routing with OpenStreetMap Data, ACM SIGSPATIAL GIS 2011. paper · code
• E. Mortensen, W. Barrett, Intelligent Scissors for Image Composition, SIGGRAPH 1995. paper