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

Source: https://www.geekswithgeeks.com/hi/dsa/bellman-ford

> एक source से सबसे छोटे रास्ते, जो negative edge weights के साथ भी काम करता है और negative cycle पहचान सकता है।

## हर 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** मौजूद है और सबसे छोटे रास्ते अपरिभाषित हैं।

```python
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 बिल्कुल नहीं कर सकता।