# Floyd-Warshall Algorithm — डेटा स्ट्रक्चर और एल्गोरिदम

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

> Intermediate nodes पर dynamic programming का उपयोग करते हुए, एक weighted graph में सभी जोड़ों के बीच सबसे छोटे रास्ते।

## हर node एक पड़ाव के रूप में

Floyd-Warshall **हर जोड़े** के nodes के बीच सबसे छोटे रास्ते निकालता है। यह हर node `k` को बीच के पड़ाव के रूप में आज़माता है: `dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`। सभी `k` पर विचार करने के बाद, `dist[i][j]` असली सबसे छोटा रास्ता रखता है।

## क्रियान्वयन

सीधे edge weights से शुरू करें (जहाँ edge नहीं वहाँ infinity, diagonal पर 0), फिर `k, i, j` पर तीन-स्तरीय loop चलाएँ।

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

## कब चुनें

Floyd-Warshall तब चुनें जब छोटे-मध्यम graph (`V` कुछ सौ तक) पर **सभी जोड़ों** के सबसे छोटे रास्ते चाहिए। एक ही source के लिए, Dijkstra या Bellman-Ford कहीं सस्ता है।