Dijkstra vs Bellman-Ford
Dijkstra whenever every edge weight is non-negative, because it is much faster. Bellman-Ford when negative weights are possible, or when you need to detect a negative cycle, which Dijkstra cannot do at all.
Both find shortest paths from one source. Dijkstra is greedy: it repeatedly takes the closest unsettled node and treats its distance as final. That commitment is what makes it fast and what makes negative edges fatal, because a negative edge can improve a node that has already been settled. Bellman-Ford makes no such commitment and simply relaxes every edge repeatedly until nothing improves.
Side by side
| Dimension | Dijkstra | Bellman-Ford |
|---|---|---|
| Time | O(E log V) with a heap | O(V times E) |
| Negative weights | Incorrect, silently | Correct |
| Negative cycles | Cannot detect | Detects them with one extra pass |
| Approach | Greedy, settles nodes in order | Repeated relaxation of all edges |
| Data structure | Priority queue | Plain edge list |
| Early exit | Yes, once the target is settled | No, though it can stop if a pass changes nothing |
| Distributed use | Awkward | Natural, this is distance-vector routing |
When to pick each
Dijkstra
- Road networks, latency graphs, and anything where a weight is a physical cost and therefore non-negative.
- Large graphs, where the difference between E log V and V times E decides whether it finishes.
- You only need the distance to one target and can stop as soon as it is settled.
Bellman-Ford
- Weights can be negative, such as a graph where some edges represent a gain rather than a cost.
- You need to know whether a negative cycle exists, for instance detecting an arbitrage loop in currency exchange rates.
- The graph is small enough that the extra factor does not matter, and you want the simpler implementation.
Running Dijkstra on a graph with negative edges and trusting the output. It does not throw, it does not loop forever, and it returns numbers that look like distances. It settles a node, then a negative edge later offers a shorter route that is ignored because the node is already final. If negative weights are even possible in your input, the choice is made for you.
Questions people ask
Why does Bellman-Ford run exactly n-1 times?
A shortest path in a graph of n nodes visits at most n-1 edges, since a path repeating a node would contain a cycle and could be shortened. Each pass extends every known shortest path by at least one edge, so n-1 passes are enough.
How does the negative cycle check work?
Run one extra pass. After n-1 passes everything should be final, so if any edge still relaxes, some path keeps getting cheaper, which can only happen if you can loop round a negative cycle indefinitely.
What about all pairs?
Floyd-Warshall, at O(n cubed), which is simpler than running a single-source algorithm from every node and handles negative edges. For sparse graphs, Johnson's algorithm uses Bellman-Ford once to reweight and then runs Dijkstra from each node.