Shortest Path

Core Concepts

Shortest path — a path between two vertices with minimum total edge weight (or fewest edges for unweighted graphs). Multiple shortest paths may tie in cost.

Relaxation — the core primitive: if dist[u] + w(u,v) < dist[v], update dist[v]. All shortest-path algorithms differ only in how they order and repeat relaxation until convergence.

Single-source shortest path (SSSP) — minimum-cost paths from one source to all other vertices. Produces a distance array and optionally a predecessor array for path reconstruction.

All-pairs shortest path (APSP) — minimum-cost paths between every pair of vertices. Produces a V×V distance matrix.

Negative weight edge — an edge with weight < 0. Dijkstra produces silently wrong results; Bellman-Ford handles them correctly.

Negative weight cycle — a cycle whose total weight is negative; shortest path is undefined because indefinite looping reduces cost without bound. Bellman-Ford detects these.

Relaxation order — the sequence in which edges are relaxed determines correctness and efficiency. Dijkstra relaxes in non-decreasing tentative-distance order (greedy); Bellman-Ford relaxes all edges V−1 times (exhaustive); Floyd-Warshall relaxes over intermediate vertices.

DAG (directed acyclic graph) — admits shortest paths even with negative edges because no cycles exist. Topological sort gives a valid single-pass relaxation order.

---

Internal Representation

The adjacency list + 1D dist array + min-heap combination is standard for Dijkstra. Floyd-Warshall updates the adjacency matrix in-place. Bellman-Ford iterates an edge list.

---

Types / Variants

---

Key Algorithms

BFS (Unweighted Shortest Path)

Finds shortest path by hop count in an unweighted graph; each BFS level corresponds to one additional hop. Correctness: nodes are dequeued in non-decreasing hop order, so the first visit is optimal. O(V+E) time, O(V) space.

Dijkstra's Algorithm

Finds SSSP in graphs with non-negative edge weights. Maintains a min-heap of (tentative_dist, node); greedily processes the closest unvisited node and relaxes its neighbors.

Invariant: once a node is popped from the heap, its distance is final. This invariant breaks with negative edges because a later path through a negative edge could improve an already-finalized node.

heappush(heap, (0, src))
while heap:
    d, u = heappop(heap)
    if d > dist[u]: continue          # stale entry
    for v, w in graph[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            heappush(heap, (dist[v], v))

O((V+E) log V) with binary heap.

Bellman-Ford

Finds SSSP with negative edges; detects negative cycles. Relaxes all E edges exactly V−1 times. After k iterations dist[v] holds the shortest path using at most k edges. If any distance still improves on the V-th pass, a negative cycle reachable from the source exists. O(VE) time, O(V) space.

SPFA (Shortest Path Faster Algorithm)

Queue-based Bellman-Ford: only enqueue a node when its distance improves, skipping unchanged neighbors. Average O(E) on sparse graphs; degrades to O(VE) on adversarial inputs. Negative cycle detection: if any node is enqueued V or more times, a negative cycle exists. Use when Bellman-Ford correctness is required but the graph is expected to be sparse in practice.

DAG Shortest Path

Topological sort gives a valid relaxation order; process each node in topo order and relax its outgoing edges once. Negative edges are safe because no back edges (no cycles) exist. O(V+E) time, O(V) space. The fastest SSSP algorithm when the graph is guaranteed acyclic.

Floyd-Warshall

Computes APSP by iterating over all possible intermediate vertices k: for each pair (i, j), if routing through k is cheaper, update dist[i][j].

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

O(V³) time, O(V²) space. Initialize dist[i][i] = 0 and dist[i][j] = inf for non-edges. Detect negative cycles by checking dist[i][i] < 0 after the loop. Does not handle negative cycles — presence makes all-pairs results undefined.

0-1 BFS

Shortest path when edge weights are only 0 or 1. Uses a deque: weight-0 edges push to the front (free move), weight-1 edges push to the back. Equivalent to Dijkstra but O(V+E) because the deque maintains sorted order for a two-value domain.

dq = deque([(0, src)])
while dq:
    d, u = dq.popleft()
    if d > dist[u]: continue
    for v, w in graph[u]:
        if d + w < dist[v]:
            dist[v] = d + w
            (dq.appendleft if w == 0 else dq.append)((dist[v], v))

---

Advanced Techniques

State-Augmented Dijkstra

Solves constrained shortest-path problems by expanding the state space: the heap stores (cost, node, extra_state) instead of (cost, node). The visited set keys on (node, extra_state).

Mechanism: extra_state encodes remaining budget, stops used, fuel level, or any finite discrete constraint. Each (node, state) pair is treated as an independent node in an implicitly expanded graph.

When to use over plain Dijkstra: the problem imposes a secondary constraint that makes per-node distance insufficient. Do not use when unconstrained — it multiplies the state space by the constraint dimension, changing O((V+E) log V) to O((V·K+E·K) log(V·K)).

Example: cheapest flight within k stops → heap entry (cost, city, stops_remaining).

Bellman-Ford for k-hop or Arbitrage

Runs exactly k iterations of Bellman-Ford to find shortest paths using at most k edges; or detects negative cycles in currency exchange graphs (edge weight = −log(rate), negative cycle = arbitrage opportunity).

When to use over Dijkstra: negative edges are present, or the problem bounds path length to at most k edges. For k-hop constraint specifically, k Bellman-Ford iterations is simpler than state-augmented Dijkstra. Do not use on non-negative graphs — Dijkstra is strictly faster.

k-hop implementation note: copy dist before each iteration pass to avoid within-pass propagation beyond one hop.

Virtual Nodes / Layered Graph

Transforms a problem into standard shortest path by adding virtual nodes for each "mode" or "layer". Layers connect with transition-cost edges; same-layer edges are the original graph edges.

When to use over state augmentation: the constraint has a clean graph-layer interpretation (e.g., highway vs surface roads, before-discount vs after-discount). State augmentation and layered graphs are equivalent in complexity; choose whichever makes the edge structure clearer to implement.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Negative edges with Dijkstra: the finality invariant breaks silently — the algorithm completes and returns plausible but wrong distances. There is no crash or obvious signal. Always confirm non-negative weights before choosing Dijkstra.
• Negative cycle reachability: Bellman-Ford only detects negative cycles reachable from the source. A negative cycle elsewhere in the graph is invisible. For APSP, Floyd-Warshall's dist[i][i] < 0 check covers all nodes.
• Disconnected graph: unreachable nodes keep dist = inf. Returning inf directly instead of -1 or a problem-specified sentinel is a common output bug.
• Stale heap entries: without if d > dist[u]: continue, Dijkstra re-processes outdated entries and correctness holds but runtime degrades. This guard is not optional.
• State-augmented visited key: the visited set must key on (node, extra_state), not just node. Using only node prematurely prunes paths with different remaining budget, producing wrong answers.
• Floyd-Warshall initialization: dist[i][i] must be 0 and non-edges must be inf before the triple loop. Missing dist[i][i] = 0 corrupts all paths that route through i as an intermediate.
• Bellman-Ford within-pass propagation: if dist is updated in-place during one pass, a relaxation early in the pass can feed a relaxation later in the same pass, effectively using more than one new edge per iteration. Use a copy when exactly k hops is required.
• Integer overflow in dist init: Python float('inf') is safe. In C++, use INT_MAX/2 — adding any edge weight to INT_MAX overflows to negative.
• Undirected graph with one-directional edges: add edges in both directions; forgetting the reverse direction makes the graph effectively directed.
• Multi-edges between same pair: keep only the minimum weight edge for most shortest-path algorithms; Bellman-Ford handles multi-edges naturally but Dijkstra may process redundant entries.

---

Implementation Notes

• Python heapq is a min-heap only; to simulate max-heap, negate weights.
• float('inf') supports arithmetic correctly in Python: float('inf') + 5 == float('inf').
• Initialize dist as a list of length V (or V+1 for 1-indexed), not a dict, unless the graph has string or sparse node labels.
• BFS requires either a visited set or a dist check before enqueuing; without it, runtime can become exponential on dense graphs.
• For Floyd-Warshall, copy the input matrix to a mutable 2D array before the loop — modifying the input directly causes confusion when the same matrix is both read and written.
• Python's default recursion limit (1000) makes recursive graph traversal unsafe for V > ~500; use iterative BFS/DFS.
• In state-augmented Dijkstra, the visited set grows to O(V × K); pre-allocate a 2D boolean array rather than a Python set for better constant factors.

---

Cross-Topic Relations

See graph-theory.md for graph representation, traversal, and connectivity coverage. See breadth-first-search.md for BFS mechanics and grid traversal patterns.

---

Interview Reference

Must-Know Problems

Basic SSSP

• Network Delay Time (medium) — Dijkstra; answer is max(dist.values())
• Path with Minimum Effort (medium) — Dijkstra on grid, cost = max edge weight on path
• Swim in Rising Water (hard) — Dijkstra; cost = max cell value on path

Grid Shortest Path

• Shortest Path in Binary Matrix (medium) — BFS on grid
• Minimum Obstacle Removal to Reach Corner (hard) — 0-1 BFS; removing obstacle = cost 1
• Cut Off Trees for Golf Event (hard) — repeated multi-BFS

Constrained / Augmented State

• Cheapest Flights Within K Stops (medium) — state-augmented Dijkstra or k-iteration Bellman-Ford
• Shortest Path with Alternating Colors (medium) — state (node, last_color_used)
• Minimum Cost to Reach Destination in Time (hard) — state (node, time_remaining)
• Number of Ways to Arrive at Destination (medium) — Dijkstra + path count array

APSP

• Find the City with Smallest Number of Neighbors at Threshold (medium) — Floyd-Warshall
• Evaluate Division (medium) — Floyd-Warshall on ratio graph

Negative / Bellman-Ford

• Cheapest Flights Within K Stops — Bellman-Ford k-iteration variant
• Minimum Cost to Convert String (hard) — Dijkstra on character-pair graph

Additional LeetCode Coverage

• Find the City With the Smallest Number of Neighbors at a Threshold Distance (LC 1334)

Clarification Questions to Ask

• Are edge weights non-negative? (Determines Dijkstra vs Bellman-Ford.)
• Is the graph directed or undirected? (Undirected: add edges both ways.)
• Can there be multiple edges between the same pair of nodes? (Keep minimum for correctness.)
• Is the graph guaranteed connected, or must disconnected nodes return a sentinel value?
• Is the actual path required, or just the cost?
• What are V and E? (Guides algorithm choice: O(V²) vs O((V+E) log V) vs O(V³).)

Common Interview Mistakes

• Applying Dijkstra to a graph with negative edges and trusting the output without verifying the non-negative precondition.
• Omitting if d > dist[u]: continue in Dijkstra, degrading runtime without breaking correctness — harder to notice.
• Keying the visited set on node only instead of (node, extra_state) in constrained-path problems, silently pruning valid paths.
• Returning float('inf') instead of -1 for unreachable nodes.
• Forgetting to set dist[i][i] = 0 before Floyd-Warshall.
• Building undirected graph edges in only one direction.
• Using in-place dist updates during k-hop Bellman-Ford, allowing multi-hop propagation within one pass.

Typical Follow-Up Escalations

• "Now return the actual path, not just the cost" → add prev[v] = u on each relaxation; reconstruct by walking backward from target.
• "What if some edges have negative weights?" → switch to Bellman-Ford; if DAG, topological sort + DP.
• "What if we need all-pairs distances?" → Floyd-Warshall for V ≤ 500; Johnson's algorithm for larger V with negatives.
• "Can you handle a grid with unit and zero-cost moves?" → 0-1 BFS with deque; O(V+E) vs O((V+E) log V) for Dijkstra.
• "What if the graph updates dynamically?" → re-run from affected nodes; D* or LPA* for incremental shortest path (beyond standard interviews).