What you'll learn
Two more shortest-path tools: Floyd-Warshall computes the distance between every pair of vertices in a few lines, and A* speeds up a single search by aiming at the goal — the algorithm behind game and map pathfinding.
By the end you'll be able to:
- Compute all-pairs shortest paths with Floyd-Warshall
- Explain how a heuristic guides A*
- See why A* explores far fewer nodes than Dijkstra
Floyd-Warshall (all pairs)
Instead of one source, Floyd-Warshall finds the shortest path between every pair at once. Its idea is beautifully simple dynamic programming: for each vertex k, ask "does going through k make any path i → j shorter?" Three nested loops, O(V³):
INF = float("inf")
def floyd_warshall(dist): # dist[i][j]: weight of edge i->j, INF if none
n = len(dist)
for k in range(n): # allow paths through vertex k
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist # now shortest distance between EVERY pairNote
O(V³) sounds slow, but for a dense graph where you need all pairs, it beats running Dijkstra from every vertex — and it handles negative edges (just not negative cycles).A* search
Dijkstra explores outward in all directions equally. A* adds a heuristic h(v) — an estimate of the remaining distance to the goal (e.g. straight-line distance) — and prioritizes by f(v) = g(v) + h(v), where g(v) is the cost so far. That nudges the search toward the goal, so it settles far fewer nodes.
Key idea
h = 0, A* is Dijkstra.Dijkstra vs A* on a grid
Finding a path from S to G on an open grid, here's roughly what each explores (yellow) before finding the path (purple):
Dijkstra — explores everywhere
A* — heads for the goal
Comparison
| Algorithm | Solves | Time | Note |
|---|---|---|---|
Dijkstra | One source → all | O((V+E) log V) | No heuristic |
A* | One source → one goal | O(E) with a good heuristic | Needs an admissible heuristic |
Floyd-Warshall | All pairs | O(V³) | Great for dense graphs |
Bellman-Ford | One source → all | O(V·E) | Handles negative edges |
Recap & quick check
Key takeaways
- Floyd-Warshall finds all-pairs shortest paths with three nested loops, O(V³).
- Its DP asks whether routing through vertex k shortens each path i→j.
- A* prioritizes by f(v) = g(v) + h(v): cost so far plus an estimate to the goal.
- An admissible heuristic (never overestimates) guarantees A* finds the shortest path.
- A* explores far fewer nodes than Dijkstra; with h = 0 it becomes Dijkstra.
Quick check
1. Floyd-Warshall computes:
2. In A*, the priority of a node is:
3. An 'admissible' heuristic is one that:
4. With heuristic h = 0, A* behaves like:
We've found cheapest paths. Next: connect every vertex at the lowest total cost. Next up: Module 28 — Minimum Spanning Trees.