Bellman-Ford

DSA · Advanced

Definition

Bellman-Ford relaxes all edges V−1 times to find shortest paths, even with negative weights.

Detects negative cycles where Dijkstra fails.

Diagram

Flowchart

Example: Shortest with negative edge

E = [(0, 1, 4), (0, 2, 5), (2, 1, -3)]
d = [0, float('inf'), float('inf')]
for _ in range(2):
    for u, v, w in E:
        if d[u] + w < d[v]: d[v] = d[u] + w
print(d)

Output: [0, 2, 5]

Complexity

O(V × E)

Key points

Slower than Dijkstra
Used in distance-vector routing

Interview questions

How is a negative cycle detected?

If any edge still relaxes after V−1 rounds.