Day 7 · Week 2

Dijkstra (review) & Floyd-Warshall

Level 2 · Shortest Path · 2 hrs: ~45 min theory · ~60 min code · ~15 min notes

🧠 Mental Model

Dijkstra is the greedy SSSP algorithm for non-negative weights: always expand the closest not-yet-finalized vertex, because nothing cheaper can ever improve it later. Floyd-Warshall answers a different question — all-pairs shortest paths — via dynamic programming over "which intermediate vertices are allowed."

These are the two poles of shortest-path: one source computed fast (Dijkstra), or every pair at once with dead-simple code (Floyd-Warshall). Knowing which the interviewer wants is half the battle.

⚙️ Dijkstra — Mechanics

dist[src] = 0, rest +∞; push (0, src) to a min-heap.
Pop the smallest-distance vertex u. If it's stale (popped distance > dist[u]), skip.
Relax each outgoing edge; on improvement, push the new (dist, v).
The first time a vertex is popped, its distance is final.

Why greedy is safe (and why negatives break it)

Theorem (Dijkstra correctness) With all edge weights ≥ 0, when a vertex u is first extracted from the priority queue, dist[u] = δ(src, u).

Proof sketch (exchange argument) Suppose not: let u be the first vertex extracted with dist[u] > δ(src, u). Consider a true shortest path src ⇝ u, and let y be the first vertex on it that is still in the queue, preceded by finalized x. Because x was finalized correctly, the edge (x → y) was relaxed, so dist[y] = δ(src, y) ≤ δ(src, u) < dist[u]. But then y, not u, would have been extracted first — contradiction. The step δ(src, y) ≤ δ(src, u) relies on non-negativity (a prefix of a shortest path is no longer than the whole). A negative edge later on can make the whole path cheaper than a prefix, voiding the argument. ∎

Never patch Dijkstra for negatives by re-inserting finalized nodes — worst case goes exponential. Use Bellman-Ford (Day 6) instead.

📊 Dijkstra Complexity

Priority queue	Time	Notes
Binary heap	O((V + E) log V)	The interview default.
Fibonacci heap	O(E + V log V)	Theoretically optimal; rarely coded.
Array (dense)	O(V²)	Better than heap when E ≈ V².

🔗 Floyd-Warshall — Mechanics & the DP

Let d^{(k)}[i][j] = shortest path from i to j using only intermediate vertices from the set {1, …, k}. The recurrence considers "do we route through vertex k or not?"

Recurrence: d^{(k)}[i][j] = min( d^{(k−1)}[i][j], d^{(k−1)}[i][k] + d^{(k−1)}[k][j] )

Why the recurrence is correct Any shortest path from i to j using intermediates in {1..k} either (a) doesn't use k — then it's optimal over {1..k−1}, the first term; or (b) uses k exactly once (a shortest path is simple in the absence of negative cycles), splitting into i ⇝ k and k ⇝ j, each using only {1..k−1} — the second term. Taking the min covers both cases. ∎

The k loop must be the outermost loop — that's what enforces the "intermediates ≤ k" layering. Swapping loop order is the classic bug.

Negative-cycle check: after the algorithm, if any d[i][i] < 0, vertex i lies on a negative cycle.

💻 Reference Implementation (Java)

import java.util.*;

/** Dijkstra with a binary heap. adj[u] = list of {v, w}, w ≥ 0. */
public int[] dijkstra(List<int[]>[] adj, int n, int src) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    // min-heap on distance
    PriorityQueue<int[]> pq =
        new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{src, 0});

    while (!pq.isEmpty()) {
        int[] top = pq.poll();
        int u = top[0], d = top[1];
        if (d > dist[u]) continue;              // stale entry — skip
        for (int[] e : adj[u]) {
            int v = e[0], w = e[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[]{v, dist[v]});
            }
        }
    }
    return dist;
}

/** Floyd-Warshall. d[i][j] init: 0 on diagonal, weight for edges, INF otherwise. */
public void floydWarshall(int[][] d, int n) {
    for (int k = 0; k < n; k++)              // k MUST be outermost
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] != INF && d[k][j] != INF
                        && d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
}

⚠️ Common Pitfalls

No lazy-deletion check in Dijkstra: without if (d > dist[u]) continue; you reprocess stale nodes and can TLE.

Floyd-Warshall loop order: k must be the outer loop. i,j,k order silently computes wrong answers on some graphs.

Overflow in FW: INF + INF overflows; guard both operands or use a large-but-safe sentinel.

Choosing FW when SSSP suffices: O(V³) is wasteful if you only need one source — use Dijkstra.

🎭 Problem Variances — Dijkstra & Floyd-Warshall in disguise

Dijkstra's tell is "cheapest / shortest / min cost" with non-negative weights, single source. Floyd-Warshall's tell is "between every pair" or small V with repeated queries.

Disguise / phrasing	What's really asked	Twist to handle
"Network delay / time for signal to reach all"	Dijkstra, then max dist	Answer is the farthest finalized distance
"Path with minimum effort / max-height"	Minimax path (Dijkstra variant)	Relax with max(edge, pathMax), not sum
"Maximum probability path"	Dijkstra on products	Max-heap; multiply probs (or negate logs)
"Cheapest with fuel/stops/state"	Dijkstra over augmented state	Node = (city, fuelLeft); dist keyed on full state
"Shortest between every pair, small n (≤ ~400)"	All-pairs	Floyd-Warshall O(V³)
"Evaluate division / transitive ratios"	Weighted transitive closure	FW-style products, or DFS per query
"City reachable within threshold"	All-pairs + count	FW, then count neighbors ≤ threshold

Routing rule: one source, non-negative → Dijkstra. Every pair or tiny dense graph → Floyd-Warshall. Negative edges → back to Bellman-Ford (Day 6). "Distance" can be a max or product — adapt the relaxation.

🎯 Problems

LC 1631 Path With Minimum Effort Dijkstra variant — "distance" = max edge on the path (minimax). Adapt the relaxation. Med

LC 1334 Smallest Number of Neighbors at a Threshold Distance All-pairs → Floyd-Warshall, then count reachable within the threshold. Med

LC 399 Evaluate Division Weighted graph of ratios; FW-style transitive products, or DFS per query. Med

📚 References

CLRS, 3rd ed., §24.3 — "Dijkstra's algorithm," with the greedy correctness proof (Theorem 24.6).
CLRS, §25.2 — "The Floyd-Warshall algorithm," DP derivation and structure of shortest paths.
Dijkstra, E. W. (1959) — "A note on two problems in connexion with graphs," Numerische Mathematik 1, 269–271.
Floyd, R. W. (1962) — "Algorithm 97: Shortest path," Comm. ACM 5(6), 345.
Fredman & Tarjan (1987) — Fibonacci heaps, the O(E + V log V) Dijkstra bound.

← Day 6: Bellman-Ford Day 8: Basic Union-Find →