Lesson 26.1 · Shortest Paths

Dijkstra's Algorithm

Always expand the unfinished node with the smallest known distance. With non-negative weights that distance is final, so each node is settled once.

16 min

Think of it like this

Water poured at the start spreads along pipes of different lengths. It reaches nodes in order of distance, and the moment it first arrives at a node, no later route can arrive sooner.

1.Greedy by distance

Keep dist[] (∞ except the start, which is 0) and a min-heap of (distance, node). Pop the smallest. If it's stale (larger than dist[node]), skip it. Otherwise relax each edge: if dist[u] + w < dist[v], update dist[v] and push (new distance, v).

Why it's correct: when u is popped with the smallest distance d, any other route to u would have to leave the settled region through some node with distance ≥ d and then add non-negative weights, so it can't be shorter. A negative edge breaks this argument.

Cost: O((V + E) log V) with a binary heap. Pushing duplicates and skipping stale entries ("lazy deletion") is simpler than a decrease-key operation, which Java's PriorityQueue doesn't support.

Main.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 1}, {2, 3, 5}, {3, 4, 3}};
        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]}); adj.get(e[1]).add(new int[]{e[0], e[2]}); }

        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.offer(new int[]{0, 0});                       // {distance, node}
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int d = top[0], u = top[1];
            if (d > dist[u]) continue;                   // stale entry
            for (int[] e : adj.get(u)) {
                int v = e[0], nd = d + e[1];
                if (nd < dist[v]) { dist[v] = nd; pq.offer(new int[]{nd, v}); }
            }
        }
        System.out.println(Arrays.toString(dist));
    }
}

Output

[0, 3, 1, 4, 7]

▶ Dry run: Dijkstra from node 0undirected: 0-1 (4), 0-2 (1), 2-1 (2), 1-3 (1), 2-3 (5), 3-4 (3)

dist(map)

0: 01: ∞2: ∞3: ∞4: ∞

heap(list)

(0, 0)

Step 1/5Start: dist[0] = 0.

Remember

Min-heap by distance; skip stale entries.
Relax: dist[u] + w < dist[v].
Non-negative weights only.

Common mistakes

Marking nodes final when pushed instead of when popped.
int overflow when adding to Integer.MAX_VALUE (check before adding, or use long).

Words used in this lesson

Relax an edge: Check whether going through u gives v a shorter distance, and update it if so.
Stale entry: A heap entry whose distance is larger than the node's current best; it is skipped.

Command Palette

Dijkstra's Algorithm

1.Greedy by distance