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” changes mainly by what you ask for and what weights are allowed
Before choosing an algorithm, separate the query shape from the graph structure. Single-source asks for one origin to many destinations; all-pairs asks for every origin. Then ask whether the graph is unweighted, a DAG, non-negatively weighted, or allowed to contain negative edges.
Memory aid: first identify the question you are asking; then identify what the edge weights permit.
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.
A shortest-path tree is the “receipt” for every distance
The distance label tells you how far a vertex is from the source; the parent pointer tells you why. Keeping one parent edge for each reachable vertex turns those choices into a tree. Follow parents backward from any target and you recover an actual shortest path.
Tree Does Not Mean “Use Only Tree Edges in the Original Graph”
The original graph can have many extra edges. The shortest-path tree simply records one predecessor choice per reachable vertex that certifies a shortest route from 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:
Relaxation asks one local question: “Did going through u improve our best route to v?”
A tentative distance is a best-known promise, not necessarily the final answer. Relaxing an edge compares the current promise for v against the route that first reaches u and then crosses that edge.
Memory aid: relaxation is not “move along this edge.” It is “use this edge to challenge the best distance we currently know.”
What differs between BFS, Dijkstra, and Bellman-Ford is purely the order in which edges get relaxed:
| Algorithm | Relaxation order | Handles negative weights? |
|---|---|---|
| BFS (deep dive) | layer by layer (implicit — all weights = 1) | n/a (unweighted) |
| Dijkstra (deep dive) | always the currently-closest unfinalized vertex | no |
| Bellman-Ford (deep dive) | every edge, every round, $V-1$ times | yes |
| DAG shortest paths (Part 7) | topological order, single pass | yes (DAG only) |
The algorithms disagree about when an estimate is trustworthy
Key Insight
Dijkstra's algorithm is, in a precise sense, "Bellman-Ford with a smarter relaxation order" — a priority queue is really just a mechanism for guessing, correctly, which edge is safe to relax next without needing to revisit it later. That guess is only guaranteed safe when weights are non-negative, which is exactly why Dijkstra's algorithm and Bellman-Ford diverge exactly there.
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.
A final distance labeling should survive every possible relaxation
Think of each edge as an attempted objection: “I can reach v more cheaply through u.” If even one edge succeeds, the distances are not finished. If every edge fails to improve anything, the labeling is locally stable; the path-witness condition ensures those labels are also achievable.
Choosing the Right Algorithm
The fastest correct algorithm is usually determined by one structural fact about the graph. Use the simplest branch whose assumptions your input actually satisfies.
Pick the algorithm by eliminating unnecessary generality
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.
An inequality becomes an edge because relaxation enforces exactly that inequality
The constraint $x_j-x_i\le c_{ij}$ can be rewritten as $x_j\le x_i+c_{ij}$. That has the same shape as a shortest-path edge condition, so encode it as the directed edge $i\to j$ with weight $c_{ij}$.
Why the super-source? It gives Bellman-Ford a path to every variable, so every constraint participates in the same system.
Negative Cycle = Contradictory Constraints
If Bellman-Ford can keep decreasing values around a directed cycle, the inequalities collectively demand an impossible decrease. In this model, negative-cycle detection becomes a direct infeasibility certificate.
Turning "A must start ≥3 after B, B must start ≥2 after C" into a Graph
Constraints $x_A - x_B \leq -3$ and $x_B - x_C \leq -2$ become edges $B \to A$ (weight $-3$) and $C \to B$ (weight $-2$), plus a super-source $S$ with zero-weight edges to $A, B, C$. Running Bellman-Ford from $S$ gives one valid schedule (e.g., $x_C = 0, x_B = -2, x_A = -5$) — shift all values by a constant to make them non-negative if needed, since only the differences matter.
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
- 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.
- 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.
- 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?).
- 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.
Next in the Series
In Part 10: Shortest Paths II — Floyd-Warshall, Johnson's & A*, we solve all-pairs shortest paths two different ways and meet the heuristic-guided search that powers GPS routing and video-game pathfinding.