Skip to main content

Shortest Path - Floyd-Warshall

Learn Shortest Path - Floyd-Warshall (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Floyd-Warshall: All-Pairs Shortest Paths Floyd-Warshall finds the shortest distance between every pair of vertices at once. It tries each vertex k as an intermediate stop: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) . Three nested loops give O(V³) time and O(V²) space, which suits small dense graphs. It works with negative edges (but not negative cycles). The outer loop must be over k .

More lessons in Graphs