Introduction
The Floyd-Warshall algorithm finds all shortest paths between the nodes in a single run. It is particular useful when the is small.
Implementation
def floydWarshall(N, adj):
distance = [[inf] * N for _ in range(N)]
for i in range(N):
for j in range(N):
if i == j:
distance[i][j] = 0
elif adj[i][j]:
distance[i][j] = adj[i][j]
for k in range(N):
for i in range(N):
for j in range(N):
distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
Complexity
- Time complexity:
- Space complexity: