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.
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.
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.
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.
$$\text{Time: } O(VE) \text{ (one Bellman-Ford)} + O(V(V+E)\log V) \text{ (V Dijkstra runs)}$$
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.
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.
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.
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.