Learn
Floyd-Warshall Algorithm
The Floyd-Warshall Algorithm computes shortest paths between all pairs of vertices in a single run. It handles negative edges but not negative cycles. It's also known as the Roy-Floyd algorithm.
For each intermediate vertex , you check if going through shortens the path from to .
function floydWarshall(graph, n):
dist = n x n matrix
initialize dist[i][j] = graph[i][j] if edge exists, else infinity
initialize dist[i][i] = 0
for k from 0 to n - 1:
for i from 0 to n - 1:
for j from 0 to n - 1:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
Loop order: You must iterate in the outer loop. This ensures paths using vertices to are computed before considering vertex .
Detecting negative cycles: After completion, check if any . A negative diagonal indicates a negative cycle.
Applications: You use Floyd-Warshall for transitive closure, finding graph diameter, all-pairs shortest paths in dense graphs, and network analysis.
Time complexity: due to three nested loops.
Space complexity: for the distance matrix.