Floyd-Warshall Algorithm

Every node as a stepping stone

Floyd-Warshall computes shortest paths between every pair of nodes. It tries each node k as an intermediate stepping stone: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After considering all k, dist[i][j] holds the true shortest path.

Implementation

Start with the direct-edge weights (infinity where no edge exists, 0 on the diagonal), then triple-loop over k, i, j.

def floyd_warshall(n, edges):
    INF = float('inf')
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Output:

# dist[i][j] = shortest distance from i to j, O(V^3) time, O(V^2) space

When to pick it

Use Floyd-Warshall when you need all-pairs shortest paths on a small-to-medium graph (V up to a few hundred). For a single source, Dijkstra or Bellman-Ford is far cheaper.