The idea: two ways to relax the same edges
This page draws one directed graph twice and runs Dijkstra's algorithm on the left and Bellman-Ford on the right, at the same time, from the same source S. Every step relaxes exactly one edge on each side, so the counters under the panels compare the work honestly. When both are done, Dijkstra's distances are checked against Bellman-Ford's, which are always right (or report that no right answer exists).
Relaxation
Both algorithms are built from one move. To relax an edge u→v with weight w is to ask: is going through u cheaper than the best way to v known so far?
relax(u, v, w):
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
parent[v] = u
At the start dist[S] = 0 and every other dist is ∞. The two algorithms differ only in which edges they relax and in what order. The counters show relaxations (edges examined) and updates (relaxations that lowered a dist). The blue arrows are the current parent pointers: the shortest-path tree so far.
Dijkstra: close the nearest vertex for good
Dijkstra keeps a priority queue of open vertices ordered by dist. It pops the smallest, closes it, and relaxes its out-edges. A closed vertex is never looked at again: an edge into a closed vertex is skipped. Each edge is relaxed once, so the total is E relaxations (fewer if some vertices are unreachable).
Closing is a promise: "no path found later can be cheaper". With non-negative weights the promise holds. Any other path to the popped vertex leaves the closed set through an open vertex whose dist is already at least as large, and the rest of that path can only add weight. Demo 1: all weights ≥ 0 shows both sides ending with the same table, Dijkstra after 10 relaxations and Bellman-Ford after 30.
How a negative edge fools Dijkstra
A negative edge breaks the "can only add weight" step. In Demo 2, S→A costs 2 and S→B costs 5, so Dijkstra pops and closes A with dist 2. Later it pops B and relaxes B→A = −4: the path S→B→A costs 1, but A is already closed, so the offer is thrown away. The edge turns red. Worse, A's wrong value has already been passed on to C, D and E, so four entries end with ✗.
A negative edge does not always cause this. It only does harm when it points into a vertex that is already closed. In Demo 3 the negative edge A→C is relaxed while C is still in the queue, so C gets its true distance before it is popped, and every entry is ✓. That is luck, not a guarantee.
Some textbook versions of Dijkstra do update a closed vertex's dist, but they still never re-relax its out-edges, so the error stays in its successors. Neither version is correct with negative weights.
Bellman-Ford: V−1 passes over every edge
Bellman-Ford trusts nothing. In each pass it relaxes every edge of a fixed list, left to right (the orange box under the right panel is the cursor).
for pass = 1 .. V-1:
changed = false
for each edge (u, v, w) in the list:
if relax(u, v, w): changed = true
if not changed: stop // early exit: every dist is final
for each edge (u, v, w): // pass V: the check
if dist[u] + w < dist[v]: report "negative cycle"
After pass k, every vertex whose shortest path uses at most k edges has its final dist. A shortest path without cycles has at most V−1 edges, so V−1 passes are always enough. The pass row of the right table shows in which pass each dist last went down.
Edge order and early exit
How many passes are needed depends on the order of the list. Demo 5 and Demo 6 use the same graph, whose shortest path to F runs along all 6 edges of a chain.
| Edge order | What a pass does | Passes | Relaxations |
|---|---|---|---|
| As listed: along the chain (Demo 6) | each edge sees its tail's final value, so pass 1 finds every distance; pass 2 changes nothing and stops | 2 | 16 |
| Reversed (Demo 5) | each pass moves the correct value only about one edge along the chain | 6 + the check pass = 7 | 56 |
The early exit is safe: if a whole pass changes nothing, the next pass would see exactly the same values, so nothing can ever change again. That quiet pass also proves there is no negative cycle. Dijkstra is not affected by the list order: it decides its own order from the queue.
Negative cycles and −∞
If a cycle has negative total weight and can be reached from S, going round it once more always makes the path cheaper. There is no shortest path, and the distance of every vertex reachable from the cycle is −∞. In Demo 4 the cycle B→C→D→B weighs 1 − 3 + 1 = −1. Bellman-Ford's passes keep changing, so after V−1 passes it runs pass V, which only checks. Every edge that could still lower a distance turns purple, and everything reachable from those edges gets −∞. A and F are not reachable from the cycle and keep their normal distances.
Dijkstra never notices. It closes each vertex once and stops, printing finite numbers for B, C, D and E that mean nothing.
DAGs: one pass in topological order
If the graph has no cycles and the edge list is sorted in topological order (every edge's tail before its head), each edge is relaxed after its tail's dist is final. One pass is then enough, with negative edges or not. Demo 7 shows pass 1 finding every distance and pass 2 confirming it, while Dijkstra still closes C too early. Doing that single pass directly, after a topological sort, is the usual DAG shortest-path algorithm, in O(V + E).
Cost comparison
| Dijkstra | Bellman-Ford | |
|---|---|---|
| Relaxations | at most E | at most V·E (fewer with early exit) |
| Time | O((V + E) log V) with a binary heap | O(V·E) |
| Negative edges | may give wrong answers | correct |
| Negative cycle | not detected; output meaningless | detected by pass V |
| Depends on edge order | no | number of passes does |
Which one to use
- All weights ≥ 0 (road lengths, latencies, costs): Dijkstra. It is much faster, and with a goal in mind A* is faster still.
- Negative weights, or you must know whether a negative cycle exists (arbitrage in currency exchange rates, constraint systems): Bellman-Ford.
- A DAG: one pass in topological order.
- All pairs: Floyd-Warshall, or Johnson's algorithm, which runs Bellman-Ford once to re-weight every edge to a non-negative value and then Dijkstra from every vertex. Adding a constant to every edge does not work: it penalizes paths with more edges.
Use Set Weight (for example A->C=-2) or Random Weights in the Options row to try your own cases on the same drawings.
What the page leaves out
- The priority queue is drawn as a sorted list. A real Dijkstra uses a binary heap with decrease-key, or pushes duplicates and skips stale entries.
- Queue-based Bellman-Ford (SPFA), which only re-relaxes edges out of vertices that changed.
- Recovering the negative cycle itself by walking parent pointers back from a flagged vertex.
- Undirected graphs: there a single negative edge already forms a negative cycle (go back and forth).