# Floyd-Warshall Algorithm — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/floyd-warshall

> All-pairs shortest paths in a weighted graph using dynamic programming over intermediate nodes.

## 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`.

```python
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.