Graph AlgosAlgorithmaka single-source shortest path, SSSP non-negative

Dijkstra's Algorithm

Single-source shortest paths on graphs with non-negative edge weights, greedily settling the closest unsettled node using a min-priority queue.

▶ VisualizePattern: Heap / Priority QueuePractice (4)
Progress

Overview

Dijkstra computes the shortest distance from one source to every node in a graph whose edge weights are all ≥ 0. It repeatedly picks the unsettled node with the smallest tentative distance, declares that distance final, and relaxes its outgoing edges (dist[v] = min(dist[v], dist[u] + w)). It is Breadth-First Search (BFS) generalised to weights: the queue that pops "oldest first" is replaced by a Priority Queue that pops "smallest distance first".

Preconditions and complexity: non-negative weights, directed or undirected, single source. With a Binary Heap over an Adjacency List it runs in O((V + E) log V); with a plain array scan for the minimum it is O(V²), which is actually preferable on dense graphs where E ≈ V². It does not work with negative edges (see the counterexample below) and cannot detect negative cycles — that is Bellman-Ford's job.

shortest pathweightednon-negativegreedypriority queueO((V + E) log V)

Intuition

A mental model before the formal terms.

Picture the graph as a network of pipes of different lengths and pour water into the source. The water front reaches nodes in order of their true distance. Dijkstra simulates the front by jumping to the next "moment of arrival": the node with the smallest tentative arrival time is the one the water reaches next, and nothing that arrives later can ever shorten that time — because water cannot flow backwards through a pipe of negative length.

How it works

  1. Set dist[s] = 0 and every other dist = ∞. Push (0, s) into a min-heap keyed by distance.
  2. Pop the smallest (d, u). If d > dist[u] this is a stale entry (a shorter path was found after it was pushed) — skip it. Otherwise u is now settled.
  3. For every edge u → v with weight w: if dist[u] + w < dist[v], set dist[v] = dist[u] + w, parent[v] = u, and push (dist[v], v). This is called relaxing the edge.
  4. Repeat until the heap is empty (or until the target is popped, if only one destination matters). Reconstruct a path by following parent from the target.
  5. Why the heap: each of the ≤ E relaxations may push one entry, and each pop/push costs O(log(heap size)) = O(log E) = O(log V). Without a heap, finding the minimum unsettled node costs O(V) per step, O(V²) total.

Why it works

Claim: when u is popped with distance d, d is the true shortest distance δ(s, u). Suppose not; then a shorter path exists and it must leave the settled set at some edge x → y with y unsettled. Since all weights are ≥ 0, dist[y] ≤ δ(s, y) ≤ δ(s, u) < d, so y would have been popped before u. Contradiction. This step uses non-negativity — with negative weights δ(s, y) ≤ δ(s, u) can fail.

Concrete failure with a negative edge: nodes A, B, C with edges A→B = 2, A→C = 3, C→B = -2. Dijkstra pops A (0), then B (2) and settles it. Later it pops C (3) and finds 3 + (-2) = 1 < 2, but B is already final (or, in the lazy variant, B was already popped so the improvement is never propagated to B's successors). The true distance to B is 1; Dijkstra reports 2.

Complexity: each node is settled once, so V pops of settled nodes; each edge relaxes at most once from its settled tail, pushing at most E entries; total O((V + E) log V).

Recognition

How to tell a problem wants this.

  • Weighted graph, all weights ≥ 0 (times, distances, costs, probabilities converted with -log).
  • "Minimum cost/time to reach", "network delay", "cheapest route".
  • Grids where each cell has an entry cost (path with minimum sum of values).
  • If the weights are all equal, downgrade to BFS Shortest Path (Unweighted); if only 0 and 1, to 0-1 BFS.
“k most frequent” → Heap / Priority Queue“weighted graph” → Shortest Path (Weighted)

Interactive visualization

Play, step, change the input. ← → and space work too.

42518103263A0B∞C∞D∞E∞F∞G∞
Priority queue (min first)
nodedist
A0
1/22All distances start at ∞ except dist[A] = 0. The priority queue always hands us the closest unsettled node, which is what makes greedy settling correct with non-negative weights.
Settled now (popped)In priority queueSettledEdge being relaxedBest-known parent edgeShortest path
PseudocodeLearn Dijkstra's Algorithm →
1dist = {v: ∞}; dist[source] = 0; pq = [(0, source)]
2while pq not empty:
3  (d, u) = pq.pop_min()
4  if d > dist[u]: continue   # stale entry
5  for (v, w) in neighbors(u):
6    if dist[u] + w < dist[v]:
7      dist[v] = dist[u] + w; parent[v] = u
8      pq.push((dist[v], v))
9path = follow parent from target back to source
Complexity
best O(V log V)
avg O((V + E) log V)
worst O((V + E) log V)
space O(V + E)
Speed

Pseudocode

1dist = {v: INF}; dist[s] = 0; heap = [(0, s)]
2while heap not empty:
3  d, u = heap.pop_min()
4  if d > dist[u]: continue      # stale entry
5  for (v, w) in adj[u]:
6    if dist[u] + w < dist[v]:
7      dist[v] = dist[u] + w; parent[v] = u
8      heap.push((dist[v], v))

Implementations

11 · Min-priority queue
2import heapq                       # heapq IS the min-heap: plain functions over a list
3from math import inf
4 
5 
6def dijkstra(adj: list[list[tuple[int, int]]], s: int) -> tuple[list[float], list[int]]:
7    """adj[u] = [(v, w), ...] with w >= 0; nodes 0..n-1.
8    Returns (dist, parent) with dist = inf for unreachable nodes."""
92 · Initialize distances
10    n = len(adj)
11    dist: list[float] = [inf] * n
12    parent = [-1] * n
13    dist[s] = 0
14    heap: list[tuple[float, int]] = [(0, s)]       # (dist, node) — tuples compare by distance first
153 · Pop the closest unsettled node
16    while heap:
17        d, u = heapq.heappop(heap)
18        if d > dist[u]:            # stale entry: a shorter path was pushed later
19            continue
204 · Relax outgoing edges
21        for v, w in adj[u]:
22            nd = d + w
23            if nd < dist[v]:
24                dist[v] = nd
25                parent[v] = u
26                heapq.heappush(heap, (nd, v))
275 · Result
28    return dist, parent
Walkthrough
  1. heapq is already a min-heap — no comparator needed; entries are (dist, node) tuples and tuple comparison starts with the distance.
  2. dist is typed list[float] because math.inf is a float; real distances stay exact ints under the hood.
  3. The stale check d > dist[u] skips entries superseded by a later, shorter push — heapq has no decrease-key.
  4. heappush(heap, (nd, v)) and heappop(heap) are module functions operating on a plain list, not methods on a heap object.
  5. parent lets callers rebuild any shortest path by walking back to the -1 sentinel.
Complexity (this implementation)
time O((V + E) log V) · space O(V + E)

Python ints are arbitrary precision — no overflow — but each heap operation carries interpreter overhead; PyPy or the O(V²) array variant can win on dense graphs.

Language notes
  • heapq only provides a min-heap; for a max-heap push negated keys.
  • If nodes are non-comparable objects, push (dist, counter, node) with an itertools.count() tiebreaker so comparison never reaches the node.
  • queue.PriorityQueue wraps heapq with locks for threads — never use it in algorithms.
Common mistakes in this language
  • Pushing (node, dist) — the heap orders by node id and the algorithm silently breaks.
  • Using dist[u] + w after popping instead of the popped d — equivalent here, but mixing the two invites stale-value bugs.
  • Rebuilding the heap with heapify inside the loop instead of pushing duplicates — turns each relaxation into O(E).
Language differences that matter here
  • Heap orientation: C++ std::priority_queue is a max-heap by default and needs greater<> (or negated keys); Python heapq is a min-heap; JavaScript/TypeScript have no heap at all, so a ~40-line binary MinHeap is hand-rolled.
  • Decrease-key: none of the four standard libraries offer it; all four versions use lazy deletion — push a new entry and skip stale ones on pop (d > dist[u]).
  • Ordering entries: C++ pairs and Python tuples compare lexicographically, so (dist, node) order matters; the JS/TS heap compares index 0 explicitly.
  • Overflow: C++ needs long long and must not compute INF + w (UB); JS/TS doubles are exact only below 2^53 and Infinity + w is safely Infinity; Python ints never overflow.

Complexity

Best
O(V log V)
Average
O((V + E) log V)
Worst
O((V + E) log V)
Space
O(V + E)

Binary heap with lazy deletion (heap may hold up to E entries; log E = O(log V)). Array-based minimum selection: O(V²), better when E ≈ V². Fibonacci heap: O(E + V log V), rarely worth it in practice.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Single-source shortest paths with non-negative weights on a sparse graph (E ≪ V²).
  • Point-to-point queries where you can stop at the target; add a heuristic to get A* Search.
  • Grid path costs (each cell has a non-negative entry cost), road networks, latency graphs.
  • Dense graphs: use the O(V²) array version instead of the heap — fewer allocations and no log factor.
Avoid it when
  • Any negative edge weight — wrong answers silently. Use Bellman-Ford (or reweight with Johnson's algorithm for all-pairs).
  • Unweighted graphs — BFS Shortest Path (Unweighted) is O(V + E) and simpler.
  • All-pairs on a dense graph with V ≤ ~500 — Floyd-Warshall is O(V³), trivially simple, and handles negative edges.
  • Weights restricted to {0, 1} — 0-1 BFS with a deque is linear.
  • "Shortest path with at most k edges" — the settle-once property breaks; use Bellman-Ford limited to k rounds or BFS over (node, hops) states.

Alternatives

Bellman-FordBFS Shortest Path (Unweighted)0-1 BFSA* SearchFloyd-Warshall
Compare: Dijkstra vs Bellman-FordCompare: BFS vs Dijkstra

Common mistakes

  • Using it with negative edges "because there is no negative cycle" — a single negative edge already breaks it (the A/B/C example above).
  • Forgetting the stale-entry check if d > dist[u]: continue; correctness survives but the algorithm degrades toward O(E²) relaxations on dense graphs.
  • Marking a node visited when pushed instead of when popped — a node can be pushed with a non-final distance and would then never be improved.
  • Storing tuples with the node first (u, d) in the heap so it orders by node id instead of distance.
  • Overflow: dist[u] + w with dist[u] = INT_MAX — skip unreachable nodes or use a sentinel that cannot overflow (or 64-bit).
  • Solving "cheapest flights within k stops" with plain Dijkstra — the hop limit invalidates the greedy settle step.

Interview patterns

  • Network delay time: run Dijkstra, answer is the max finite distance (or -1 if some node is unreachable).
  • Path with minimum effort / swim in rising water: minimise the maximum edge instead of the sum — same algorithm, relax with max(dist[u], w).
  • Probability paths: maximise a product by using a max-heap or by minimising -log p.
  • State expansion: node = (cell, remaining fuel) or (node, used discount) when one extra small dimension matters.
  • Bidirectional or target-terminated Dijkstra for a single destination.
Interview questions on this
Mock interviews

Example problems

Shortest Path in Binary MatrixmediumNetwork Delay TimemediumCheapest Flights Within K StopsmediumMin Cost to Connect All Pointsmedium