Floyd-Warshall Algorithm

हर 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 चलाएँ।

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 कहीं सस्ता है।