Bellman-Ford Algorithm

हर edge को n-1 बार relax करें

Bellman-Ford बार-बार हर edge को relax करता है (जांचता है कि उससे होकर जाने से destination की distance छोटी होती है या नहीं), कुल V-1 बार। V-1 राउंड के बाद, सभी सबसे छोटे रास्ते (जो अधिकतम V-1 edges इस्तेमाल करते हैं) मिल जाने की गारंटी है — negative weights के साथ भी।

क्रियान्वयन

मुख्य V-1 राउंड के बाद एक अतिरिक्त pass जांचता है कि कोई distance अभी भी घट सकती है या नहीं — अगर हाँ, तो एक negative cycle मौजूद है और सबसे छोटे रास्ते अपरिभाषित हैं।

def bellman_ford(n, edges, src):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            raise ValueError('negative cycle detected')
    return dist

Dijkstra बनाम Bellman-Ford

Bellman-Ford O(V*E) है — Dijkstra के O((V+E) log V) से धीमा — लेकिन negative weights संभालता है और negative cycle पहचानता है, जो Dijkstra बिल्कुल नहीं कर सकता।