---
title: "Dijkstra"
description: "Shortest path with priority queue"
source: https://vizlearn.app/algorithms/graph/dijkstra
---

# Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from one source to every other node in a graph with non-negative edge weights. It keeps a tentative distance for each node, repeatedly finalizes the unvisited node with the smallest tentative distance, and relaxes that node's outgoing edges — using a priority queue to always pull the closest frontier node out next.

Picture a board of pins, one per node, joined by strings cut to each edge's weight and left slack on the table. Grab the source pin and lift it straight up, slowly. The pins leave the table one at a time, and the order they lift off is exactly the order of their shortest distances from the source — nearest first. Whichever strings end up taut trace the shortest paths. Dijkstra is that lift, done with arithmetic instead of string: at every step it picks up the next-closest pin and asks whether the strings hanging off it pull any still-grounded pin a little higher.

The whole trick rests on one assumption: **every edge weight is non-negative.** That is what lets Dijkstra commit to a node the instant it pops — nothing it discovers later can ever beat a distance it already locked in. Allow a single negative edge and that promise breaks: a node finalized early can turn out to have a shorter path, and Dijkstra, having moved on, reports the wrong answer. The default graph shows the algorithm working; the **Negative** preset shows exactly where and why it fails. Use Dijkstra when weights are non-negative — otherwise reach for Bellman-Ford.

## How Dijkstra's Algorithm Works

Three pieces of state carry the whole algorithm: a `dist` map (the best distance known *so far* to each node, starting at 0 for the source and ∞ for everyone else), a `visited` set (the nodes whose distance is now permanent), and a priority queue of `(distance, node)` entries that hands you the smallest distance on demand.

The loop has two moves, and the order matters.

**Extract and finalize.** Pop the queue's minimum — the unvisited node `u` reachable most cheaply right now — and mark it visited. Here is the load-bearing claim: `dist[u]` is now its *true* shortest distance, final, never to be touched again. Why is that safe? Every other unvisited node sits behind a frontier that is already at distance ≥ `dist[u]`, and since no edge has negative weight, any path discovered later can only add to that — it can never sneak in under `dist[u]`. Non-negative weights are the entire load-bearing assumption. Remove them and this paragraph is a lie (see Common Mistakes).

**Relax.** For each edge `u → v` with weight `w`, check whether going through `u` beats `v`'s current best: is `dist[u] + w < dist[v]`? If so, you've found a shorter route to `v` — lower `dist[v]` to `dist[u] + w`, record `u` as `v`'s predecessor, and push the improved `(dist[v], v)` onto the queue. This single comparison is *relaxation*, and it is where every distance on the board actually changes. Some relaxations do nothing — the new route is no better — and watching them fail is as instructive as watching them succeed. How many fail depends on the graph; on the default most of them succeed.

One wrinkle from using an ordinary binary heap: when you relax a node that's already in the queue, you don't hunt down its old entry and edit it — you just push a new, smaller one. The old entry is now **stale**. It still sits in the heap with an out-of-date key, and eventually it floats to the top and gets popped. The fix is one line at the top of the loop: if the node you popped is already visited, throw the entry away and move on. Stale entries are normal, expected, and harmless — they're the price of skipping the bookkeeping a decrease-key operation would need.

## Dijkstra's Algorithm Step by Step

Run the default: the **Weighted** graph, six nodes A–F, starting at A. The directed edges and their weights are `A→B (2)`, `A→C (5)`, `B→C (1)`, `B→D (7)`, `C→D (2)`, `D→E (1)`, `D→F (3)`, `E→F (2)`. (Nodes are letters so they never blur into the distances and weights, which are all numbers.)

1. **Start.** `dist[A] = 0`, everyone else ∞. Push `(0, A)`. Queue: `[(0,A)]`.
2. **Finalize A** (the only entry). Relax its edges: `A→B` lowers `dist[B]` from ∞ to **2**; `A→C` lowers `dist[C]` from ∞ to **5**. Queue: `[(2,B), (5,C)]`.
3. **Finalize B** (`dist = 2`, the smallest). Now the interesting one: `B→C` offers `2 + 1 = 3`, which beats the 5 we already had, so `dist[C]` drops from 5 to **3**. Note what just happened — the *two-edge* path `A→B→C` (cost 3) beat the *one-edge* path `A→C` (cost 5). Fewer hops, longer path; this is the exact thing BFS cannot see, because BFS counts edges and these weights are not all 1. Then `B→D` sets `dist[D]` to **9**. Queue: `[(3,C), (5,C), (9,D)]` — note there are now *two* entries for C, the stale `(5,C)` and the fresh `(3,C)`.
4. **Finalize C** (`dist = 3`). Relax `C→D`: `3 + 2 = 5` beats 9, so `dist[D]` drops from 9 to **5**. Queue: `[(5,C), (5,D), (9,D)]`.
5. **Pop `(5,C)` — stale.** C is already finalized, so this is the obsolete entry left over from step 2. Discard it, do nothing. Queue: `[(5,D), (9,D)]`.
6. **Finalize D** (`dist = 5`). Relax `D→E`: `dist[E]` becomes **6**. Relax `D→F`: `dist[F]` becomes **8**. Queue: `[(6,E), (8,F), (9,D)]`.
7. **Finalize E** (`dist = 6`). Relax `E→F`: `6 + 2 = 8`, which is *not* less than the 8 we already have, so nothing changes — a no-op relaxation. Queue: `[(8,F), (9,D)]`.
8. **Finalize F** (`dist = 8`). No outgoing edges. Queue: `[(9,D)]`.
9. **Pop `(9,D)` — stale.** D is finalized; discard. Queue empty — done.

Final distances: `A:0, B:2, C:3, D:5, E:6, F:8`. Read the order nodes were finalized — A, B, C, D, E, F at distances 0, 2, 3, 5, 6, 8 — and you see the headline property as a single sweep: **non-decreasing, every time.** That monotonic order is *why* finalizing on pop is safe: when you pop C at 3, every other entry left in the queue is already ≥ 3, and no non-negative edge can pull any of them back below it.

## Time and Space Complexity

| Operation | Count | Cost each | Total |
|---|---|---|---|
| Push / pop (binary heap) | O(V + E) | O(log V) | O((V + E) log V) |
| Relaxation checks | O(E) | O(1) | O(E) |

| Case | Time | Space |
|---|---|---|
| All (binary heap) | O((V + E) log V) | O(V + E) |

Each edge triggers at most one successful relaxation, so the heap holds at most O(E) entries over the run; each push and pop costs O(log V). Switch to a Fibonacci heap with decrease-key in place of lazy duplicates — O(V) extract-mins and O(E) decrease-keys — and the bound tightens to O(E + V log V) in theory, though the constants rarely pay off in practice. Swapping the heap type alone keeps every lazy duplicate and its pop. Space is the `dist` map and `visited` set (O(V)) plus the heap (O(E)).

## Edge Cases

- **Unreachable nodes.** A node with no incoming path is never pushed, never finalized, and keeps its distance of ∞. Dijkstra computes shortest paths to the source's *reachable* set, nothing more.
- **Single node.** Push it, pop it, finalize it at distance 0, done.
- **Ties.** Two queue entries with equal keys are both valid next picks; which you finalize first doesn't change any final distance. (This lesson breaks ties by node id so the trace is reproducible.)
- **Zero-weight edges.** Perfectly fine — zero is non-negative. Two nodes can finalize at the same distance, one right after the other.
- **A single target.** If you only need the distance to one node, you can stop the instant you finalize *that* node — its distance is already permanent. The rest of the queue is irrelevant.

## Common Mistakes

1. **Negative edge weights.** This is the one that matters. Dijkstra's whole correctness rests on "a finalized distance can never improve," and that holds only when no edge is negative. The **Negative** preset shows it breaking on purpose: B finalizes at distance 2, and *then* the edge `C→B` of weight −5 reveals a path `A→C→B` worth −2 — strictly shorter. But B is already locked, so the improvement is rejected and the algorithm reports the wrong answer, 2 instead of −2. The run even ends with B still ringed in red to drive it home. No amount of cleverness in the queue saves you; the assumption is gone. For graphs with negative edges, reach for Bellman-Ford.
2. **Relaxing into a finalized node and "fixing" it.** A close cousin of the above. If you ever find yourself wanting to lower the distance of a visited node, your graph has a negative edge and you're using the wrong algorithm.
3. **Using BFS on a weighted graph.** BFS finds the path with the *fewest edges*, which is guaranteed to be the shortest path only when every edge costs the same. Step 3 above is the counterexample in miniature: the cheapest route to C takes more edges than the direct one.
4. **Forgetting the stale check.** Skip the `if u in visited: continue` line and you'll reprocess nodes through their obsolete queue entries — extra work. With this code's `v not in visited` guard the distances stay correct, but a variant without that guard can go wrong; the check keeps each node to one expansion.
5. **Marking a node visited when you push it instead of when you pop it.** That's the BFS habit, and it's wrong here: a node's distance isn't final until it's the *cheapest* thing left, which you only know at pop time. Mark on pop, not on push.

## A Note on Simplification

Two honest caveats. First, the priority queue is drawn as a fully sorted row so you can read "smallest is at the front" at a glance — a real binary heap only guarantees the minimum sits at the top, with the rest partially ordered, not a tidy sorted list. Second, the code shown skips relaxing already-finalized nodes (`v not in visited`), which is one common, correct-for-non-negative-weights implementation; other textbook variants drop that guard and lean entirely on the pop-time stale check. They agree on every distance when weights are non-negative, and none of them is guaranteed correct once an edge is negative. This is an explainer built to make the *mechanism* visible, not a drop-in replacement for a hardened shortest-path library.