Part 9: Shortest Paths I — Dijkstra & Bellman-Ford

Shortest-Path Fundamentals

"Shortest path" is really five related questions, not one:

• Single-source: distances from one vertex to every other vertex (BFS, Dijkstra, Bellman-Ford).
• Single-destination: distances from every vertex to one target — solved by running a single-source algorithm on the reversed graph.
• Single-pair: distance between one specific source and target — no asymptotically faster general algorithm exists than solving single-source and reading off one answer, though heuristics like A* (Part 10) exploit extra structure to prune the search.
• All-pairs: distances between every pair of vertices (Floyd-Warshall, Johnson's — Part 10).

Shortest-Path Trees

Every single-source algorithm we've built (BFS's parent map, Dijkstra's and Bellman-Ford's relaxation-driven parent updates) actually computes more than just distances — it computes a shortest-path tree: a spanning tree (of the reachable vertices) where the tree-path from the source to any vertex $v$ is a shortest path to $v$ in the original graph. This is why reconstructing an actual shortest path, not just its length, is always just a matter of walking parent pointers backward from the target to the source.

Relaxation as a Unifying Idea

Every shortest-path algorithm in this series — without exception — is built from exactly one primitive operation, first named formally in Part 2:

$$\textbf{Relax}(u, v, w)\text{: if } d[u] + w(u,v) < d[v] \text{, set } d[v] \leftarrow d[u] + w(u,v) \text{ and } \pi[v] \leftarrow u$$

What differs between BFS, Dijkstra, and Bellman-Ford is purely the order in which edges get relaxed:

Optimality Conditions

A clean way to verify a claimed set of distances $d[\cdot]$ without re-running any algorithm: $d[\cdot]$ is correct if and only if (1) $d[\text{source}] = 0$, (2) every edge $(u,v)$ satisfies $d[v] \leq d[u] + w(u,v)$ (no further relaxation is possible — the triangle inequality for shortest paths), and (3) every $d[v]$ with $v$ reachable equals the weight of some actual path. This is exactly the property Bellman-Ford's final "extra round" checks in reverse — if condition (2) is ever violated, the claimed distances are wrong.

Choosing the Right Algorithm

flowchart TD
    A["What kind of graph?"] -->|"Unweighted"| B["BFS — O(V+E)"]
    A -->|"DAG"| C["Topological DP — O(V+E)"]
    A -->|"Weighted, non-negative"| D["Dijkstra — O((V+E) log V)"]
    A -->|"Weighted, negative allowed"| E["Bellman-Ford — O(VE)"]
    A -->|"All-pairs needed"| F["Floyd-Warshall or Johnson's (Part 10)"]
            

Difference Constraints

A genuinely surprising application: a system of inequalities of the form $x_j - x_i \leq c_{ij}$ (common in scheduling — "task $j$ must start at least $c_{ij}$ after task $i$") can be solved directly with Bellman-Ford. Build a graph with one vertex per variable, an edge $i \to j$ with weight $c_{ij}$ for every constraint, and a super-source connected to every vertex with weight-0 edges. Run Bellman-Ford from the super-source: the resulting distances $d[\cdot]$ are a valid assignment satisfying every constraint simultaneously, and a detected negative cycle means the constraint system is infeasible — no valid assignment exists at all.

A Glimpse of Specialized Techniques

A few refinements worth knowing exist, each trading generality for speed in a specific setting: Dial's algorithm replaces Dijkstra's binary heap with an array of buckets when edge weights are small non-negative integers, achieving $O(V + E + W)$ where $W$ is the maximum weight. Bidirectional Dijkstra (the weighted cousin of bidirectional BFS from Part 5) searches from both the source and target simultaneously. Replacement paths ask "what's the shortest path if this one edge is removed?" for every edge on the current shortest path — useful for fault-tolerant routing. We'll meet A* — arguably the most important of these refinements — in full in Part 10.

Exercises

1. Verify the optimality conditions by hand on the worked example from the Dijkstra deep dive — confirm every edge satisfies $d[v] \leq d[u] + w(u,v)$ for the final distances.
2. Explain why single-destination shortest paths reduce to single-source shortest paths on the reversed graph, but this trick does not help for single-pair queries.
3. Model the constraints $x - y \leq 2$, $y - z \leq 3$, $z - x \leq -6$ as a graph, run Bellman-Ford, and show the system is infeasible (hint: sum the three constraints — what do you get?).
4. Challenge: Implement Dial's algorithm (bucket-based Dijkstra) for a graph with integer weights in $[0, 10]$, and compare its running time against a binary-heap Dijkstra on a large sparse graph.

Conclusion & Next Steps

Every shortest-path algorithm is relaxation with a different edge order, verifiable by the same three optimality conditions, and — via difference constraints — solves scheduling problems that don't look like graphs at all until you draw them as one. Single-source is done; next, we tackle the case where you need distances between every pair of vertices at once.