Graph AlgosGraph Algorithms

Floyd-Warshall

All-pairs shortest paths by dynamic programming over the set of allowed intermediate nodes: three nested loops, O(V³), handles negative edges.

Learn Floyd-Warshall →

Weighted graph — One edge per line: "A B 4". At most 7 nodes (the table is n×n).

	A	B	C	D	E
A	0	3	∞	∞	8
B	∞	0	1	7	∞
C	2	∞	0	1	∞
D	∞	∞	∞	0	2
E	4	∞	∞	∞	0

1/39Initialize the 5×5 matrix from the edge weights: 0 on the diagonal, ∞ where no edge exists. dist[i][j] means "best path from i to j using no intermediate nodes yet".

Row k / column k (paths through k)Cell being updatedImproved in this k-phaseDiagonal (always 0)

PseudocodeLearn Floyd-Warshall →

1dist[i][j] = w(i,j) if edge, 0 if i == j, else ∞
2for k in nodes:          # allowed intermediate
3  for i in nodes:
4    for j in nodes:
5      if dist[i][k] + dist[k][j] < dist[i][j]:
6        dist[i][j] = dist[i][k] + dist[k][j]
7return dist

Complexity

best O(V³)

avg O(V³)

worst O(V³)

space O(V²)

Speed