All-Pairs Shortest Paths
Running Dijkstra or Bellman-Ford once from every vertex trivially solves all-pairs shortest paths, at a cost of $V$ times the single-source cost. Two smarter approaches exist, aimed at different graph densities.
First ask: “Do I need every pair, or just one target?”
Part 10 splits into two very different goals. Floyd-Warshall and Johnson's precompute distances between all pairs of vertices; A* spends its effort on one source-target query and uses extra geometric or domain knowledge to avoid exploring irrelevant regions.
Floyd-Warshall (Preview)
Floyd-Warshall computes all $V^2$ pairwise distances in a single, beautifully compact $O(V^3)$ dynamic program: for each intermediate vertex $k$ in turn, check whether routing through $k$ improves the distance between every pair $(i,j)$. No priority queue, no edge sorting — just three nested loops.
The DP State to Remember
After round $k$, $D^{(k)}[i,j]$ is the best path from $i$ to $j$ whose internal vertices are allowed to come only from the first $k$ vertices. Each round asks one binary question: “Is the best path still the old one, or is it better if we force it to pass through the newly allowed vertex $k$?”
Floyd-Warshall repeatedly asks: “Does going through $k$ make this pair cheaper?”
The algorithm never grows a search frontier. It improves a distance table. For every pair $(i,j)$, vertex $k$ is considered as a possible middle stop. If $i o k o j$ is cheaper than the best route known so far, the matrix entry is replaced.
Memory hook: Floyd-Warshall = every possible middle vertex, for every ordered pair.
Key Insight
Floyd-Warshall's $O(V^3)$ beats running Dijkstra $V$ times — $O(V(V+E)\log V)$ — exactly when the graph is dense ($E$ close to $V^2$), since then $V \cdot E \log V$ dwarfs $V^3$. On sparse graphs, repeated Dijkstra (or Johnson's algorithm, next) wins instead.
Warshall's Transitive Closure
A close relative solves a simpler question: not "what is the distance," but merely "does any path exist?" Replace Floyd-Warshall's min/plus arithmetic with OR/AND on booleans, and the same three-loop structure computes the transitive closure of a relation — the reachability matrix $R$ where $R_{ij} = \text{true}$ iff $j$ is reachable from $i$. This is literally the same algorithmic skeleton solving a Boolean version of the problem, which is why the two names (Floyd's and Warshall's) are so often mentioned in the same breath.
Same three loops; different algebra
Floyd-Warshall asks whether a route through $k$ is cheaper. Warshall asks whether a route through $k$ makes $j$ reachable at all. The control flow is identical; only the operation inside the innermost loop changes.
Johnson's Algorithm
Johnson's algorithm targets sparse graphs with possibly-negative weights — exactly where Floyd-Warshall's $O(V^3)$ is wasteful and plain Dijkstra can't be used directly. The trick: add a super-source connected to every vertex with zero-weight edges, run Bellman-Ford once from it to get potentials $h(v)$, then reweight every edge as $w'(u,v) = w(u,v) + h(u) - h(v)$ — a transformation that provably makes every edge weight non-negative without changing which path is shortest. Now Dijkstra can be run safely from every vertex on the reweighted graph, and the true distances are recovered by undoing the shift.
Why Reweighting Does Not Change the Best Path
Along any fixed $s\to t$ path, the internal potential terms telescope: $-h(v_1)+h(v_1)$, $-h(v_2)+h(v_2)$, and so on cancel. Every $s\to t$ path therefore receives the same additive shift $h(s)-h(t)$. If path $P_1$ was cheaper than $P_2$ before reweighting, it is still cheaper afterward.
$$\text{Time: } O(VE) \text{ (one Bellman-Ford)} + O(V(V+E)\log V) \text{ (V Dijkstra runs)}$$
Johnson uses Bellman-Ford once to make Dijkstra legal everywhere
The potentials $h(v)$ act like a change of coordinate system for edge weights. They remove negative edges while preserving the ranking of complete paths between each source and target.
On a sparse graph, this beats Floyd-Warshall's flat $O(V^3)$ by a wide margin — a genuinely elegant example of one algorithm (Bellman-Ford) making another (Dijkstra) applicable where it otherwise couldn't be used.
A* Search
A* answers a single-pair query faster than Dijkstra by using a heuristic $h(v)$ — an estimate of the remaining distance from $v$ to the target — to prioritize exploration toward the goal rather than expanding outward equally in every direction. It orders its priority queue by $f(v) = g(v) + h(v)$, where $g(v)$ is the actual distance-so-far (exactly Dijkstra's $d[v]$) and $h(v)$ is the heuristic guess.
Interpret the Three Numbers
$g(v)$ is money already spent and therefore known exactly. $h(v)$ is an optimistic estimate of what remains. $f(v)$ is the best-looking estimated total trip cost, so A* expands the frontier vertex with the smallest $f$.
A* spends effort on vertices that look promising for this target
Dijkstra ranks the frontier only by distance already traveled, $g$. A* adds a goal estimate, $h$, so vertices that are slightly farther from the start can still be preferred if they appear much closer to the destination.
Two properties determine whether A* is trustworthy: a heuristic is admissible if it never overestimates the true remaining distance ($h(v) \leq \text{true distance}(v, \text{target})$) — this alone guarantees A* finds the optimal path. A heuristic is consistent (or monotone) if $h(u) \leq w(u,v) + h(v)$ for every edge — a stronger condition that additionally guarantees A* never needs to re-expand a finalized vertex, exactly like Dijkstra. Manhattan distance (grid movement, no diagonals) and Euclidean distance (straight-line movement) are the two most common admissible heuristics for spatial pathfinding.
Admissible means “optimistic”; consistent means “locally self-consistent”
Admissible
The heuristic may be too small, but never too large. It never tells A* the remaining trip is more expensive than it truly is, so the optimal route cannot be unfairly hidden behind an inflated estimate.
Consistent
Moving across one edge cannot make the heuristic drop by more than that edge costs. This is the heuristic version of the triangle inequality and makes $f$ values behave monotonically along a search path.
A* Is Dijkstra with h(v) = 0
Set the heuristic to the constant function $h(v) = 0$ everywhere (trivially admissible and consistent), and A* becomes exactly Dijkstra's algorithm. Every guarantee Dijkstra has is a special case of what A* guarantees more generally — a satisfying way to see the whole family of shortest-path algorithms in this series as one continuum rather than a list of unrelated tricks.
Which Part 10 tool should you reach for?
Exercises
- Explain, using the reweighting formula, why $w'(u,v) = w(u,v) + h(u) - h(v)$ leaves the shortest path between any fixed pair of vertices unchanged even though individual edge weights change (hint: consider what happens when you sum $w'$ along an entire path).
- For a small graph of your choosing, determine whether Floyd-Warshall or Johnson's algorithm would be faster in practice, based on its density.
- Prove that the zero heuristic $h(v) = 0$ is always both admissible and consistent, for any graph with non-negative weights.
- Challenge: Construct a heuristic that is admissible but not consistent, and demonstrate a case where A* using it re-expands a vertex it had already finalized.
Conclusion & Next Steps
All-pairs shortest paths (Floyd-Warshall for dense graphs, Johnson's for sparse ones with negative weights) and heuristic-guided single-pair search (A*) round out the shortest-path family entirely. Every distance question this series will ever ask reduces to one of these algorithms. Next, we leave shortest paths behind and build the theory of trees from the ground up.
Next in the Series
In Part 11: Trees & Minimum Spanning Trees, we formalize tree theory, meet the Matrix-Tree theorem, and put Kruskal's and Prim's algorithms in their full theoretical context.