Floyd-Warshall Algorithm

Introduction

The Floyd-Warshall algorithm finds all shortest paths between the nodes in a single run. It is particular useful when the $n$ 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: $O(n^3)$
• Space complexity: $O(n^2)$