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 .