Shortest Paths

Formal setup. We have a directed weighted graph G = (V, E, w) where w: E → ℝ assigns a real-valued weight to each edge. (Undirected graphs are handled by replacing each undirected edge {u,v} with two directed edges (u,v) and (v,u) of the same weight.) A path from s to t is a sequence of vertices s = v₀, v₁, …, vₖ = t where each (vᵢ, vᵢ₊₁) ∈ E. The weight of a path is the sum of its edge weights. The shortest path from s to t is the path of minimum total weight; its weight is written δ(s, t).

Variants:

• Single-source (SSSP): Given source s, compute δ(s, v) for all v ∈ V. This is the canonical problem.
• Single-target: Compute δ(v, t) for all v. Equivalent to SSSP on the reversed graph.
• Single-pair: Compute δ(s, t) for specific s and t. In general, no known algorithm is asymptotically faster than SSSP for this.
• All-pairs (APSP): Compute δ(u, v) for all u, v ∈ V.

Negative edges and negative cycles. Negative-weight edges are fine as long as no negative-weight cycle is reachable from the source — because then you could loop forever and make paths arbitrarily short, so δ(s, t) = −∞. Dijkstra requires non-negative edges. Bellman-Ford detects negative cycles. Floyd-Warshall can detect them too.

The predecessor subgraph. Besides distances, we usually also want the actual path. We maintain π[v] = the predecessor of v on the shortest-path tree, which defines a tree rooted at s where the unique path from s to each v is a shortest path.

# Graph represented as adjacency list: {u: [(v, w), ...]}
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 3), ('C', 1)],
    'C': [('B', 1), ('D', 5)],
    'D': []
}
# δ(A, D) = 6  via  A -> C -> B -> D

Every shortest-path algorithm is built on a single operation called relaxation. It is the atomic update step that all the algorithms share.

We maintain an estimate d[v] of the true shortest-path distance δ(s, v). Initially, d[s] = 0 (the distance from s to itself is 0) and d[v] = ∞ for all other v. We also maintain π[v] = NIL for all v (no predecessor yet).

To relax edge (u, v) with weight w(u,v), we ask: Is the current best path to v worse than going through u? If d[u] + w(u,v) < d[v], then update:

d[v] = d[u] + w(u,v)
π[v] = u

This is the entire mechanism. The deep theorem underlying all the algorithms is:

Optimal substructure of shortest paths: Any subpath of a shortest path is itself a shortest path.

Proof sketch: If the path s→…→u→…→v is shortest, then the segment s→…→u must also be shortest (if a shorter s→u path existed, we could substitute it and get a shorter s→v path, contradiction).

This means: once we correctly set d[u] = δ(s,u), relaxing (u,v) can only give us d[v] ≤ δ(s,u) + w(u,v) = δ(s,v) if v's shortest path goes through u. The algorithms differ only in which edges they relax and in what order.

Upper-bound property: d[v] is always ≥ δ(s,v). Relaxation never overshoots — it can only decrease estimates.

Convergence property: If s → v₁ → v₂ → … → vₖ is a shortest path, and we relax the edges in order (s,v₁), (v₁,v₂), …, (vₖ₋₁, vₖ), then after these relaxations, d[vₖ] = δ(s, vₖ).

def relax(u, v, w, d, pi):
    """Relax edge (u->v) with weight w."""
    if d[u] + w < d[v]:
        d[v] = d[u] + w
        pi[v] = u
        return True  # relaxation occurred
    return False

The idea. Dijkstra's algorithm (Edsger Dijkstra, 1959) solves SSSP on graphs with non-negative edge weights. It is a greedy algorithm: at each step, it permanently finalizes the shortest distance to the unvisited vertex with the smallest current estimate.

Intuition — the wavefront analogy. Imagine pouring water into node s. Water spreads outward in all directions, reaching each node at a time proportional to its true shortest-path distance. Dijkstra simulates this: we always process the next closest unfinalized node. Because all edge weights are non-negative, a node we finalize can never be reached sooner by a later path.

Algorithm (using a min-priority queue):

1. Initialize d[s]=0, d[v]=∞ for v≠s. Insert all vertices into a min-priority queue Q keyed by d.
2. While Q is not empty: a. u = EXTRACT-MIN(Q) // the unvisited vertex with smallest d[u] b. For each edge (u, v) with weight w:
   • Relax (u, v). If d[v] decreased, DECREASE-KEY(v, d[v]) in Q.

Correctness. The key invariant: when u is extracted from Q, d[u] = δ(s, u). Proof by induction: At the first extraction (s itself), d[s]=0=δ(s,s). Suppose all extractions so far were correct. Let u be the next extracted vertex. Assume for contradiction that d[u] > δ(s,u). Then the true shortest path goes through some unfinalized vertex y. But d[y] ≤ δ(s,y) ≤ δ(s,u) < d[u], so y would have been extracted before u — contradiction. (This argument uses non-negative weights to ensure δ(s,y) ≤ δ(s,u).)

Complexity. With a binary min-heap: O((V + E) log V). With a Fibonacci heap: O(E + V log V) — optimal for dense graphs. In practice, a binary heap or even a simple array works well depending on graph density.

The non-negative requirement. If a negative edge (u,v) exists, then finalizing u might not be final — a path through a later node with d[w] > d[u] might reach v more cheaply via a negative edge. Dijkstra would have already finalized v incorrectly.

import heapq

def dijkstra(graph, source):
    """graph: {u: [(v, w), ...]}. Returns (dist, prev) dicts."""
    dist = {v: float('inf') for v in graph}
    prev = {v: None for v in graph}
    dist[source] = 0
    # Min-heap: (distance, vertex)
    pq = [(0, source)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:   # stale entry
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(pq, (dist[v], v))

    return dist, prev

def reconstruct(prev, target):
    path = []
    while target is not None:
        path.append(target)
        target = prev[target]
    return path[::-1]

Motivation. Dijkstra breaks on negative-weight edges. Real-world scenarios where this matters include currency arbitrage (negative log-exchange rates), routing with metric adjustments, and difference-constraint systems. Bellman-Ford solves SSSP correctly for graphs with negative edges (but no negative cycles), and can detect negative cycles.

The idea — dynamic programming over path length. Let d^(k)[v] = the weight of the shortest path from s to v using at most k edges. Key insight: the shortest path in a graph with |V| vertices has at most |V|−1 edges (assuming no negative cycles, since a longer simple path would revisit a vertex, and we could remove cycles). So d^(|V|-1)[v] = δ(s,v).

Recurrence: d^(k)[v] = min(d^(k−1)[v], min over (u,v)∈E of d^(k−1)[u] + w(u,v)).

Algorithm (CLRS formulation):

1. Initialize d[s]=0, d[v]=∞ for v≠s.
2. Repeat |V|−1 times: for each edge (u,v) ∈ E, relax (u,v).
3. Negative-cycle detection: Repeat for each edge (u,v): if d[u] + w(u,v) < d[v], a negative cycle is reachable → report it.

Why |V|−1 iterations? After iteration k, d[v] = shortest path using ≤ k edges. The longest simple path has |V|−1 edges, so |V|−1 iterations suffice.

Negative cycle detection. If after |V|−1 iterations any edge (u,v) can still be relaxed, there must be a negative-weight cycle reachable from s: you could keep going around the cycle and decrease distances indefinitely.

Complexity. O(V · E) — slower than Dijkstra, but handles the general case.

SPFA (Shortest Path Faster Algorithm). A common optimization: maintain a queue of vertices whose d values changed, and only process those. Average case much faster, but worst case still O(VE). Don't use SPFA in competitive programming when you need guaranteed performance — adversarial cases exist.

def bellman_ford(graph, vertices, source):
    """
    graph: list of (u, v, w) edge triples
    vertices: list of all vertex names
    Returns (dist, prev) or raises if negative cycle found.
    """
    dist = {v: float('inf') for v in vertices}
    prev = {v: None for v in vertices}
    dist[source] = 0

    n = len(vertices)
    for _ in range(n - 1):          # |V|-1 relaxation passes
        for u, v, w in graph:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u

    # Negative-cycle detection
    for u, v, w in graph:
        if dist[u] + w < dist[v]:
            raise ValueError("Graph contains a negative-weight cycle")

    return dist, prev

Understanding why these algorithms are correct is just as important as knowing how to run them. The key theorems (from CLRS Chapter 24) deserve careful attention.

Triangle inequality: δ(s,v) ≤ δ(s,u) + w(u,v) for any edge (u,v). This just says you can't do better by going the long way.

Upper-bound property: For any vertex v, d[v] ≥ δ(s,v) always. Once d[v] = δ(s,v), it never changes. Proof: d[v] starts at ∞ and only decreases. Induction shows relaxation never makes d[v] < δ(s,v) because d[u] ≥ δ(s,u) always, so d[u] + w ≥ δ(s,u) + w ≥ δ(s,v).

Path-relaxation property: If p = (v₀, v₁, …, vₖ) is any shortest path and we relax the edges in order (not necessarily consecutively), then d[vₖ] = δ(s,vₖ). This is why Bellman-Ford works: after i passes, the algorithm has effectively relaxed every path of length ≤ i in the right order by exhaustive enumeration.

Dijkstra's correctness reduces to: when we extract u from the priority queue, the only paths that could beat d[u] would have to go through some other vertex y still in the queue with d[y] ≤ d[u]. But then any path through y to u would have weight ≥ d[y] + 0 ≥ d[u] (since all subsequent edges are non-negative). So d[u] is already optimal.

Key conceptual takeaway: Dijkstra's correctness requires non-negative weights to ensure that 'extracting the minimum' is permanent — no future shorter path can appear. Bellman-Ford avoids this by not finalizing anything prematurely: it just keeps relaxing until convergence.

The problem. Sometimes we need δ(u,v) for every pair (u,v) — not just from one source. Running Dijkstra from every vertex works (O(V(E + V log V))), but Floyd-Warshall offers a beautifully simple O(V³) dynamic programming solution that handles negative edges (but not negative cycles).

The recurrence. Number the vertices 1 through n. Define:

d^(k)[i][j] = weight of shortest path from i to j using only vertices {1, 2, …, k} as intermediates.

Base case: d^(0)[i][j] = w(i,j) if edge (i,j) exists, 0 if i=j, ∞ otherwise.

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

Interpretation: The shortest path from i to j through intermediates ⊆ {1,…,k} either (a) doesn't use vertex k at all, or (b) goes i → k → j, where both legs use only intermediates ⊆ {1,…,k−1}.

After processing all k from 1 to n, d^(n)[i][j] = δ(i,j).

Implementation. Three nested loops — the order matters: k is the outermost loop.

Detecting negative cycles. After running Floyd-Warshall, if d[i][i] < 0 for any i, then there is a negative-weight cycle containing i.

Predecessor matrix. Maintain π[i][j] = the predecessor of j on the shortest path from i to j. Update during the recurrence to reconstruct paths.

Why O(V³) is sometimes preferable. For dense graphs (E ≈ V²), running Dijkstra from each source is O(V · (E + V log V)) = O(V³ + V² log V) ≈ O(V³ log V) — slightly worse than Floyd-Warshall's clean O(V³). Floyd-Warshall is also very cache-friendly and has a tiny constant.

def floyd_warshall(W):
    """
    W: n×n weight matrix (float('inf') for no edge, 0 on diagonal)
    Returns dist matrix and predecessor matrix.
    """
    n = len(W)
    dist = [row[:] for row in W]          # deep copy
    pred = [[None]*n for _ in range(n)]

    # Initialize predecessor: pred[i][j] = i if edge (i,j) exists
    for i in range(n):
        for j in range(n):
            if i != j and W[i][j] < float('inf'):
                pred[i][j] = i

    for k in range(n):                    # intermediate vertex
        for i in range(n):                # source
            for j in range(n):            # destination
                through_k = dist[i][k] + dist[k][j]
                if through_k < dist[i][j]:
                    dist[i][j] = through_k
                    pred[i][j] = pred[k][j]  # path goes through k->j

    # Check for negative cycles
    for i in range(n):
        if dist[i][i] < 0:
            raise ValueError(f"Negative cycle detected involving vertex {i}")

    return dist, pred

Motivation. Dijkstra computes shortest paths from a source to all vertices. But if we only care about reaching one specific target t, exploring the entire graph wastes work. A* (Hart, Nilsson, Raphael 1968) uses domain-specific heuristic knowledge to guide the search toward t, dramatically reducing the number of nodes explored.

The key idea: f = g + h. A* assigns each node v a priority:

• g(v) = d[v] = exact shortest-path distance from source s (computed so far)
• h(v) = heuristic estimate of distance from v to target t
• f(v) = g(v) + h(v) = estimated total path cost through v

A* uses a min-priority queue ordered by f(v). It is exactly Dijkstra if h ≡ 0.

Admissibility. The heuristic h is admissible if h(v) ≤ δ(v, t) for all v — it never overestimates. With an admissible heuristic, A* is guaranteed to find the optimal path.

Consistency (monotonicity). h is consistent if for every edge (u,v): h(u) ≤ w(u,v) + h(v). (Triangle inequality in heuristic space.) Consistency implies admissibility, and ensures that when A* pops a node, its g-value is final — just like Dijkstra. This avoids re-processing nodes.

Example heuristics:

• Grid/road networks: Euclidean distance or Manhattan distance to target (both admissible and consistent)
• 15-puzzle: number of misplaced tiles (admissible), or sum of Manhattan distances of each tile (consistent and much better)

Why A works.* The f-values form a consistent lower bound on path costs. A* never finalizes a node whose true cost could be beaten, because h(t)=0 means when t is extracted, g(t) is the true shortest distance.

Optimality conditions. If h is consistent, A* expands nodes in non-decreasing order of their true distance — optimal. If h is merely admissible (not consistent), A* still finds an optimal path but may re-expand nodes.

Weighted A.* Using h' = ε·h with ε > 1 gives a suboptimal solution at most ε times optimal, but explores far fewer nodes. Common in game AI where near-optimal is fine.

import heapq

def astar(graph, source, target, h):
    """
    graph: {u: [(v, w), ...]}
    h: heuristic function h(v) -> estimated distance to target
    Returns shortest path distance and path.
    """
    g = {source: 0}
    prev = {source: None}
    # (f_score, g_score, vertex)
    pq = [(h(source), 0, source)]

    while pq:
        f, cost, u = heapq.heappop(pq)
        if u == target:
            # Reconstruct path
            path = []
            while u is not None:
                path.append(u)
                u = prev[u]
            return cost, path[::-1]

        if cost > g.get(u, float('inf')):
            continue   # stale entry

        for v, w in graph[u]:
            new_g = g[u] + w
            if new_g < g.get(v, float('inf')):
                g[v] = new_g
                prev[v] = u
                heapq.heappush(pq, (new_g + h(v), new_g, v))

    return float('inf'), []   # target unreachable

Handling negative edges — the full picture. There are three regimes:

1. All edge weights ≥ 0: Use Dijkstra. O((V+E) log V).
2. Negative edges, no negative cycles: Use Bellman-Ford. O(VE).
3. Negative cycles reachable from source: δ(s, v) = −∞ for nodes reachable via the cycle. Bellman-Ford detects this.

DAG SSSP — the fastest approach. If the graph is a DAG (Directed Acyclic Graph), we can solve SSSP in O(V+E) — faster than Dijkstra! The trick: process vertices in topological order. Since there are no back-edges in a DAG, once we've processed u in topological order, no later vertex can relax edges into u. Negative edges are fine (there are no cycles).

Algorithm: topological sort → then for each vertex u in that order, relax all edges from u.

Johnson's algorithm for APSP with negative edges. Running Floyd-Warshall is O(V³). What if the graph is sparse (E << V²)? Running Bellman-Ford from each source is O(V²E). Johnson's algorithm (1977) is smarter: re-weight edges to make all weights non-negative (using one Bellman-Ford run), then run Dijkstra from each source. Total: O(VE + V(E + V log V)) = O(V² log V + VE) — much better for sparse graphs.

The re-weighting trick. Add a new source node s' with zero-weight edges to every vertex. Run Bellman-Ford from s' to get h[v] = δ(s', v). Define new weight ŵ(u,v) = w(u,v) + h[u] − h[v]. Claim: ŵ(u,v) ≥ 0 always (by triangle inequality). Moreover, any shortest path under w is also shortest under ŵ (the h values cancel along any path between the same endpoints).

# DAG SSSP in O(V+E)
from collections import deque

def dag_sssp(graph, order, source):
    """
    graph: {u: [(v, w), ...]}
    order: topological order of vertices
    Returns shortest distances from source.
    """
    dist = {v: float('inf') for v in order}
    dist[source] = 0

    for u in order:
        if dist[u] == float('inf'):
            continue     # unreachable, skip
        for v, w in graph.get(u, []):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    return dist

Choosing the right shortest-path algorithm requires matching the algorithm's assumptions to your problem's constraints. Here is the definitive decision framework:

When BFS beats Dijkstra. On unweighted graphs (or graphs where all weights are 1), BFS computes single-source shortest paths in O(V+E) — don't use Dijkstra with a heap when BFS will do.

Dense vs. sparse. For dense graphs (E ≈ V²), Floyd-Warshall's O(V³) matches Dijkstra-from-each-source. For sparse graphs, Johnson's algorithm or repeated Dijkstra wins.

Practical notes. Dijkstra with a simple binary heap is the workhouse of production code — it has excellent cache behavior and the constant factors are small. Fibonacci heap's O(1) decrease-key sounds great in theory but has high constants in practice. Many competitive programmers use Dijkstra with a lazy-deletion heap (push stale entries, skip with 'if d > dist[u]: continue') rather than implementing decrease-key at all.