Floyd-Warshall
The Intuition
Floyd-Warshall answers "for every pair of nodes, what is the shortest distance between them?" in one shot. The full output is a square table.
The starting table is what you already know from the edges. If there is a direct edge from i to j with weight w, dist[i][j] is w. If there is no direct edge, dist[i][j] is "very large". Distance from a node to itself is 0.
Now improve the table. Walk through every node k from 0 to V-1, and for every pair (i, j), check whether stopping at k makes the trip shorter. If dist[i][k] + dist[k][j] is less than the current dist[i][j], update. After all V values of k have been tried, every shortest path has been considered.
The reason this works: imagine the shortest path from i to j uses some set of intermediate nodes. The first time the outer loop reaches the highest-numbered intermediate node, the algorithm has already computed shortest paths that use only lower-numbered intermediates. The update step extends those into a shortest path that uses the new intermediate too. Eventually every shortest path has its "moment" in the outer loop.
The cost is V cubed because three nested loops each run V times. For 100 nodes that is a million operations, which finishes instantly. For 1000 nodes it is a billion, which is slow but still possible. For 10000 nodes you should pick a different approach (run Dijkstra from each source if all weights are non-negative, or Johnson's algorithm if they are not).
Negative weights are fine. A negative cycle is detected by checking the diagonal at the end. If any dist[i][i] is below zero, that node sits on a cycle whose total weight is negative, which means there is no real shortest path.
The pattern transfers beyond shortest distance. If you replace "+ and min" with "and / or", the same loop structure computes "is there a path from i to j" for every pair. That is called transitive closure. If you replace it with "× and max", the loop computes "what is the most reliable path" given edge probabilities.
All-pairs shortest paths on a small or medium graph (up to a few hundred or a thousand nodes). Transitive closure. Detecting negative cycles. Computing graph diameter. Anytime you need answers between every possible pair of nodes.
- The graph has thousands of nodes (V cubed is too slow)
- You only need paths from one source (use Dijkstra or Bellman-Ford)
- The graph is sparse and weights are non-negative (running Dijkstra V times is faster)
Variations:
- Transitive closure: Replace addition with logical OR and min with logical AND. The result tells you, for each pair, whether any path exists.
- Most reliable path: Replace addition with multiplication and min with max. Useful when edge weights are probabilities of success.
- Path reconstruction: Keep a "next hop" matrix updated alongside the distance matrix. When you update dist[i][j] through k, set next[i][j] to next[i][k].
- the source and target are the same (distance is 0)
- a node with no outgoing edges (its row stays at infinity except the diagonal)
- multiple edges between the same pair (keep the smallest)
- a sentinel value too close to overflow (cap at half of the int range and use early-exit on infinity)
Key Points
- •Use this when you need the shortest distance between every pair of nodes, not just one source.
- •The whole graph is stored as a V by V table where dist[i][j] is the best known distance from i to j.
- •The trick is to try every node k as a possible "stopover" between i and j.
- •For each pair (i, j), check if going i to k to j is shorter than the current dist[i][j]. If yes, update.
- •Three nested loops. The outer loop is the stopover k. The inner two loops are i and j.
- •Works with negative edges. If any dist[i][i] becomes negative, a negative cycle exists.
Code Template
1 def floyd_warshall(n, edges):
2 """
3 Shortest distance between every pair of nodes.
4 n: number of nodes (0..n-1).
5 edges: list of (u, v, w) directed edges.
6 Returns the full distance matrix.
7 """
8 INF = float('inf')
9 # Start with infinity everywhere, except a node to itself is 0.
10 dist = [[INF] * n for _ in range(n)]
11 for i in range(n):
12 dist[i][i] = 0
13 for u, v, w in edges:
14 # If multiple edges exist, keep the smallest.
15 if w < dist[u][v]:
16 dist[u][v] = w
17
18 # The key step. Try every node k as a stopover.
19 # After the k-th outer iteration, dist[i][j] is the best path that uses
20 # only nodes 0..k as stopovers.
21 for k in range(n):
22 for i in range(n):
23 if dist[i][k] == INF:
24 continue
25 for j in range(n):
26 if dist[i][k] + dist[k][j] < dist[i][j]:
27 dist[i][j] = dist[i][k] + dist[k][j]
28 return dist
29
30 def has_negative_cycle(dist):
31 """A negative cycle exists if any node has a negative distance to itself."""
32 for i in range(len(dist)):
33 if dist[i][i] < 0:
34 return True
35 return False
36
37 def reconstruct_path(n, edges, source, target):
38 """Bonus: also returns the actual path, not just the distance."""
39 INF = float('inf')
40 dist = [[INF] * n for _ in range(n)]
41 nxt = [[None] * n for _ in range(n)]
42 for i in range(n):
43 dist[i][i] = 0
44 for u, v, w in edges:
45 if w < dist[u][v]:
46 dist[u][v] = w
47 nxt[u][v] = v
48
49 for k in range(n):
50 for i in range(n):
51 for j in range(n):
52 if dist[i][k] + dist[k][j] < dist[i][j]:
53 dist[i][j] = dist[i][k] + dist[k][j]
54 nxt[i][j] = nxt[i][k]
55
56 if nxt[source][target] is None:
57 return None
58 path = [source]
59 while source != target:
60 source = nxt[source][target]
61 path.append(source)
62 return pathCommon Mistakes
- Putting i or j as the outermost loop instead of k (this gives wrong answers because intermediate stopovers must be added in order)
- Initializing dist[i][i] to anything other than 0
- Using a "very large" sentinel that overflows when added to an edge weight
- Forgetting that this is O(V^3) and trying it on a graph with thousands of nodes