The Bellman-Ford algorithm, explained

Dijkstra's algorithm fails when an edge can have a negative weight, because a longer path might become cheaper later. Bellman-Ford handles this by being more patient: it simply tries every edge again and again.

A shortest path never needs more than V − 1 edges, so repeating the process V − 1 times is enough.

How it works

• Set the start distance to 0 and every other distance to infinity.
• Go through every edge and update the distance of its end node if going through that edge is shorter.
• Repeat this V − 1 times.
• Do one more pass. If any distance still improves, there is a negative cycle and no shortest path exists.

A small example

Take these directed edges and start from A:

A>B:4  A>C:5  B>C:-3  C>D:2

Distances from A:  A 0, B 4, C 1, D 3

C is cheaper through B (4 + −3 = 1) than directly (5).

What to know about its cost

• O(V · E) time.
• Uses O(V) space.
• Works with any weights and detects negative cycles.

Where it works well

• Handles negative weights.
• Reports a negative cycle instead of looping forever.

Where it struggles

• Slower than Dijkstra for ordinary weights.
• Only finds paths from one starting node at a time.

Try it yourself

Open the Graph Algorithms experiment, enter these edges (A>B:4, A>C:5, B>C:-3, C>D:2), choose Bellman-Ford and start from A, and step through it. Then try a different graph and watch how the result changes.

Open the Graph Algorithms experiment