Dijkstra vs Bellman-Ford

Updated October 21, 2026

Shortest PathAlgorithmintermediate

Dijkstra and Bellman-Ford are both shortest path. Play them side by side below, then see exactly where they diverge.

Either player can stop before each decision and ask what happens next: turn on Predict mode in its top bar.

Dijkstra

Repeatedly settle the unsettled vertex with the smallest tentative distance and relax its edges.

Shortest distances from 0 on a undirected weighted graph. Every vertex starts at infinity except 0 at 0. Repeat: settle the unsettled vertex with the smallest distance, then relax its edges. With no negative weights, a settled distance can never be beaten.

SELECT MINIMUM -> RELAX neighbours -> UPDATE distances. Settled vertices lock. The priority queue is visible.

Bellman-Ford

Full topic

Relax every edge V-1 times. A further improvement means a negative cycle.

Bellman-Ford from 0. No settling: relax every edge, then do it again, 4 times at most, since a shortest path uses at most 4 edges. Negative weights are fine. If a further pass still improves something, the graph has a negative cycle and distances mean nothing.

Whole-graph relaxation passes. Distances settle pass by pass. A V-th pass that changes anything flags a negative cycle.

How they differ

Both find shortest paths from one source by relaxing edges. They differ in how many times. Dijkstra settles the closest unsettled vertex and relaxes its edges once, which is O((V + E) log V) with a binary heap, and it requires non-negative weights. Bellman-Ford relaxes every edge V-1 times, O(V * E), and handles negative weights instead - a further pass that still improves a distance means a negative cycle.

The run shown here takes 13 steps for Dijkstra and 9 steps for Bellman-Ford (Bellman-Ford from 0). That count moves with the input - use the example tabs above either player to see it change.

What each operation costs, for Dijkstra and Bellman-Ford side by side.
Cost	Dijkstra	Bellman-Ford
best	`O((V + E) log V)`	`O(E)`
average	`O((V + E) log V)`	`O(V * E)`
worst	`O((V + E) log V)`	`O(V * E)`
space	`O(V)`	`O(V)`