# Bellman-Ford Algorithm — Data Structures & Algorithms

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

> Shortest paths from one source that also works with negative edge weights, and can detect negative cycles.

## Relax every edge, n-1 times

Bellman-Ford **relaxes every edge** (checks if going through it shortens the destination's distance) repeatedly, `V-1` times. After `V-1` rounds, all shortest paths (which use at most `V-1` edges) are guaranteed found — even with negative weights.

## Implementation

One extra pass after the main `V-1` rounds checks if any distance can still shrink — if so, a **negative cycle** exists and shortest paths are undefined.

```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 vs Bellman-Ford

Bellman-Ford is `O(V*E)` — slower than Dijkstra's `O((V+E) log V)` — but handles negative weights and detects negative cycles, which Dijkstra cannot do at all.