Dijkstra's algorithm
mediumWhen a node comes off the priority queue it is final - no unexplored route can beat it. Set an edge weight negative to watch that greedy argument fail.
O((V + E) log V)Space O(V)Saved in this browser - no sign-up, nothing sent anywhere.
How dijkstra's algorithm works
Dijkstra grows a region of settled nodes outward from the source, always absorbing the closest unsettled node next. A priority queue hands back the node with the smallest tentative distance; the moment it comes off, that distance is final - any other route would have to exit through a node that is already further away.
The only operation is relaxation: does going through u make v cheaper? On the default graph, settling D at distance 2 relaxes E to 2 + 5 = 7; later B offers 4 + 3 = 7, a tie, so nothing changes. Every improvement pushes a fresh queue entry rather than editing the old one.
That push-instead-of-edit strategy is the lazy variant implemented here. The queue can hold several entries for one node, so each pop is checked: if its distance is worse than dist[u], it is stale - discard it and move on. The greedy argument requires non-negative weights; a single negative edge breaks the 'settled is final' promise.
Step by step
- All distances start at infinity except A at 0. The queue holds one entry, (0, A); nothing is settled.
- Settle A. Relaxing its edges writes dist[B] = 4 and dist[D] = 2, and pushes both nodes onto the queue.
- D is the cheapest entry at 2 - settle it. Its edges relax E to 2 + 5 = 7 and G to 2 + 7 = 9.
- Settle B at 4. It offers E a route of 4 + 3 = 7 - a tie with the existing 7, not an improvement, so nothing is written.
- Settle E at 7, relaxing F to 11 and H to 10. Then G settles at 9; its offer to H, 9 + 1 = 10, ties and is ignored.
- C settles at 10 and offers F 10 + 2 = 12 - worse than 11, rejected. H and then F settle, and the queue empties.
- Final distances from A: B 4, C 10, D 2, E 7, F 11, G 9, H 10. The relaxations that survived form the shortest-path tree.
Complexity
| Worst case time | O((V + E) log V) |
|---|---|
| Space | O(V) |
Fails on negative weights: a settled node can turn out to be wrong.
Reference implementation
Python
import heapq
def dijkstra(adj, start):
dist = {u: float("inf") for u in adj}
dist[start] = 0
prev = {}
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # stale entry, already improved
for v, w in adj[u]:
nd = d + w
if nd < dist[v]: # relax
dist[v] = nd
prev[v] = u
heapq.heappush(pq, (nd, v))
return dist, prevJavaScript
function dijkstra(adj, start) {
const dist = new Map([...adj.keys()].map((u) => [u, Infinity]));
dist.set(start, 0);
const prev = new Map();
// A real implementation uses a binary heap; a sorted array is
// clearer and fine for small graphs.
const pq = [[0, start]];
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]);
const [d, u] = pq.shift();
if (d > dist.get(u)) continue;
for (const { to: v, w } of adj.get(u) ?? []) {
const nd = d + w;
if (nd < dist.get(v)) {
dist.set(v, nd);
prev.set(v, u);
pq.push([nd, v]);
}
}
}
return { dist, prev };
}Java
static Map<String,Integer> dijkstra(Map<String,List<int[]>> adj, String start) {
Map<String,Integer> dist = new HashMap<>();
PriorityQueue<Object[]> pq =
new PriorityQueue<>(Comparator.comparingInt(a -> (int) a[0]));
dist.put(start, 0);
pq.add(new Object[]{0, start});
while (!pq.isEmpty()) {
Object[] top = pq.poll();
int d = (int) top[0];
String u = (String) top[1];
if (d > dist.getOrDefault(u, Integer.MAX_VALUE)) continue;
// relax each outgoing edge ...
}
return dist;
}Worth noticing
Settled means finished, permanently
When a node comes off the priority queue with the smallest tentative distance, no unexplored route can beat it - every other path would have to leave through a node that is already further away. That is the greedy argument, and it is why a node is never revisited.
Relaxation is the only operation
'Is going through u a cheaper way to reach v than what I have?' If yes, write down the better distance. Bellman-Ford, Floyd-Warshall and A* all do exactly this - they differ only in what order they relax.
Negative weights break it
The greedy argument assumes adding an edge can never reduce a distance. Set a weight to a negative number and a settled node can turn out to have been wrong - but Dijkstra has already moved on. Use Bellman-Ford instead.
The stale-entry check matters
Most implementations push a new entry rather than decreasing a key in place, so the queue can hold several entries for one node. Skipping any whose distance is worse than the recorded one keeps things correct and costs one comparison.
Common pitfalls
- Running it with negative edge weights. The greedy proof assumes extending a path never shortens it; one negative edge and a settled node can be wrong. Use Bellman-Ford instead.
- Skipping the stale-entry check. Pushing duplicates is fine, but each pop must be ignored when its distance exceeds dist[u], or you reprocess nodes with outdated values.
- Settling a node at push time instead of pop time. A node can be discovered via an expensive route first; committing early locks in the wrong distance.
- Using it for longest paths by negating weights. Negation creates negative edges, which is precisely the input Dijkstra cannot handle.
- Forgetting the predecessor map. Distances alone cannot reproduce the route - record prev[v] = u at each successful relaxation and walk it backwards.
Where it is used
- Road navigation - GPS routing is Dijkstra at heart, usually accelerated with heuristics and preprocessing.
- Link-state network routing: OSPF has each router run Dijkstra over the topology it has learned.
- Interview staples like Network Delay Time and Path With Minimum Effort, both direct applications.
- The base of A* - add an admissible heuristic to Dijkstra and you get goal-directed search.
Frequently asked questions
What is the time and space complexity of Dijkstra's algorithm?
O((V + E) log V) with a binary heap: each edge can push one queue entry, and every push or pop costs log V. Space is O(V) for distances and predecessors - the queue can briefly hold extra stale entries in this lazy variant.
When does Dijkstra fail?
On negative edge weights. The algorithm settles a node permanently the moment it leaves the queue; a negative edge discovered later could still shorten that node's distance, but Dijkstra never rechecks. Set one weight negative in the visualizer and compare against Bellman-Ford.
What is the difference between Dijkstra and BFS?
The container. BFS uses a plain queue and finds fewest-edge paths; Dijkstra uses a priority queue keyed on accumulated weight and finds cheapest paths. On a graph where every edge weighs 1 they behave identically - Dijkstra generalises BFS to unequal costs.
Why does the priority queue hold duplicate entries?
Because pushing a fresh entry on every improvement is simpler than decrease-key, which most standard heaps do not support. The cost is stale leftovers, handled by one comparison per pop: if the popped distance is worse than dist[u], discard it.