templates · Shortest paths & spanning trees

Dijkstra (shortest path, weights ≥ 0)

  • "Cheapest", "fastest" or "minimum cost" path, and edges have different, non-negative weights
  • Network routing, delivery times, map directions: one start, many destinations
  • The cost of a path is built step by step (sum, max, or product of probabilities)

Dijkstra

the one rule

The invariant

When a node is popped with d == dist[u], that cost is final: no cheaper path to it can appear later.

write it from memory

The template

javajava.util.*
/** Cheapest cost from src to every node; edges are {u, v, w} with w >= 0. -1 = unreachable. */static long[] shortest(int n, int[][] edges, int src) {    List<List<int[]>> adj = new ArrayList<>();    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());    for (int[] e : edges) adj.get(e[0]).add(new int[] {e[1], e[2]}); // directed u → v, weight w    long[] dist = new long[n];    Arrays.fill(dist, Long.MAX_VALUE);                // "infinity" until a path is found    PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0])); // {cost, node}    dist[src] = 0;    pq.offer(new long[] {0, src});    while (!pq.isEmpty()) {        long[] top = pq.poll();        long d = top[0];        int u = (int) top[1];        if (d > dist[u]) continue;                    // stale entry: u was already settled cheaper        for (int[] edge : adj.get(u)) {            int v = edge[0];            long nd = d + edge[1];                    // cost through u, in long so it cannot overflow            if (nd < dist[v]) {                dist[v] = nd;                pq.offer(new long[] {nd, v});         // push again; the old entry turns stale            }        }    }    for (int i = 0; i < n; i++) if (dist[i] == Long.MAX_VALUE) dist[i] = -1;    return dist;}

Java's PriorityQueue has no "decrease key". So push a fresh entry, and skip the old one when it pops: that is the stale line.

fill in the blanks — only these lines change per problem

  1. line 5How the graph is given: directed here; add both directions for an undirected road map, or use the grid's neighbours.
  2. line 10The start. One source here; for "reach any of these" push all of them at cost 0.
  3. line 18How a path's cost grows: d + w here, max(d, w) for Path With Minimum Effort, d * p (with a max-heap) for probability.
  4. line 25What to report: every distance, the largest one (Network Delay Time), or -1 if some node is unreachable.

complexity

What it costs

time O((V + E) log V)
Each successful relax pushes once into the heap, so at most E + 1 entries; each push and poll costs O(log E) = O(log V).
space O(V + E)
The adjacency list, the dist array, and up to E stale and live entries in the heap.

watch out

Common bugs

  • Leaving out if (d > dist[u]) continue. Old entries get processed again, and it can turn very slow.
  • Adding costs in int. Long paths of big weights overflow; keep dist in long.
  • Using it with negative edge weights. A popped node may not be final any more; use Bellman–Ford.

use it

Practise it on

learn it properly