Dijkstra's algorithm settles the closest node and never revisits it. That's only safe when edges can't be negative: otherwise a longer detour can end with a negative edge and come out shorter. Negative lengths are natural when edges are costs and gains, such as fees and rebates, energy used and recovered, or exchange rates taken as logarithms.
Bellman–Ford doesn't try to be clever about order. Every node gets a distance (0 for the start, ∞ otherwise). Then, in each pass, it checks every edge u→v once: if going through u is shorter than v's current distance, lower it. That check is called relaxing the edge.
If some cycle has negative total length, going round it again and again makes paths as short as you like: there is no shortest path. Bellman–Ford detects this with one extra pass. After V − 1 passes everything should be final, so if pass V still lowers a distance, a negative cycle must be to blame. Following the best-path edges backwards from that node leads into the cycle.
A distance ∞ B has a distance C start of the edge being checked
Numbers under the nodes are their current distances; blue edges are the best paths found so far. Each pass checks the edges in alphabetical order (A→B, A→E, B→C, …), and a distance only changes when the new path is strictly shorter. An edge can only lower anything if its start node's distance has changed since the edge was last checked; the others are passed over in one step.
| Dijkstra | Bellman–Ford | |
|---|---|---|
| Time | O((V + E) log V) | O(V · E) |
| Negative edges | Wrong answers | Fine |
| Negative cycles | Not detected | Detected |
The order of the edges doesn't change the answer, only how many passes it takes. In the example, the edges happen to come in a helpful order; in the worst case it takes all V − 1 passes.