- Current
- Has a distance
- Edge used
- Path
- Negative cycle
Bellman–Ford algorithm
Dijkstra's algorithm breaks when an edge has a negative length, like a road that pays you a toll instead of charging one. The Bellman–Ford algorithm does not: it simply checks every edge over and over until nothing improves, and it can even tell when a cycle makes distances fall forever. Click a node to start from it and step through the passes. Press Play to watch the search, or Step and Back to go one step at a time. Drag the step slider to jump anywhere. Every edge is one-way, as its arrow shows, and the number on it is its length, which can be negative. Click a node to make it the start; switch the click to Goal and click another node to see the shortest path to it at the end. The number on each node is its distance so far. Tick Add a negative cycle to see how Bellman–Ford finds one. New graph makes another graph; choose how many nodes and edges it has. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Click a node to make it the start. To see a path at the end, switch the click to Goal and click another node.
- Press Play, or use Step and Back to move one step at a time. Drag the step slider to jump anywhere.
- Tick Add a negative cycle to see Bellman–Ford find one. New graph makes another graph to try.
How Bellman–Ford works
Give the start distance 0 and every other node infinity. Then make passes: in each pass, check every edge u → v once. If u has a distance and dist(u) plus the edge's length is shorter than dist(v), lower dist(v) and remember u as the way there. After pass k, every shortest path that uses at most k edges is known. A shortest path visits each node at most once, so it has at most n − 1 edges, and n − 1 passes always suffice. If a whole pass changes nothing, the search can stop early.
Finding a negative cycle
If a cycle's edges add up to less than zero, going round it once more always makes a path shorter, so there is no shortest path at all. Bellman–Ford notices: after n − 1 passes, one more pass should change nothing. If an edge can still be relaxed, a negative cycle is reachable from the start, and following the remembered nodes back from that edge leads into it. In the app, the cycle is drawn in red.
Frequently asked questions
What is the Bellman–Ford algorithm?
An algorithm that finds the shortest paths from one start to every other node in a graph whose edges may have negative lengths. It relaxes every edge in repeated passes, and it reports a negative cycle if one can be reached from the start.
Why does Dijkstra's algorithm fail with negative edges?
Dijkstra makes a node's distance final as soon as it is the nearest in the queue. A negative edge found later can still lead back to that node by a shorter way, so the final distance can be wrong. Bellman–Ford never makes a distance final early; it keeps checking every edge.
Why n − 1 passes?
A shortest path never needs to visit a node twice, so it has at most n − 1 edges. Each pass extends the known shortest paths by at least one edge, so after n − 1 passes all of them are found.
How fast is Bellman–Ford?
Each pass checks all E edges and there are at most V − 1 passes, so the work grows with V × E. That is slower than Dijkstra's algorithm, which is why Bellman–Ford is used when edges can be negative.
Is my graph sent anywhere?
No. The graph is made and searched in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor