Graphs

Dijkstra's Algorithm

Shortest paths with non-negative weights using a priority queue.

Hard, about 90 minutes to practise.

1Understand

The idea

Dijkstra's algorithm always expands the closest unfinished node, taken from a priority queue. With non-negative weights, the first time a node is popped its distance is final. Skip stale heap entries whose distance is larger than the best known, and the whole search runs in O(E log V).

Intuition

Dijkstra always expands the closest unfinished node, taken from a priority queue. With non-negative weights, the first time a node is popped its distance is final.

Skip stale heap entries whose distance is larger than the best known, Python's heapq has no decrease-key, so lazy deletion is normal. Negative weights need Bellman-Ford instead.

The result is shortest distances (and parents, if you store them) from the source.

What you will be able to do

  • Skip stale heap entries
  • Know why negative weights break it

When to use it

  • Weighted edges, cheapest / fastest route
  • Network delay time
  • Minimum effort path on a grid

2See it

Walkthrough

Dijkstra from s

Edges 0-1:1, 0-2:4, 1-2:1, relax with a min-heap.

1 / 5

pop 0
0:0[0] root

dist[0]=0; push (0, node). Greedy: finalize the closest unsettled node.

heappush(pq, (0, start))

Live template

Line 1 active

1dist = {src: 0}; heap = [(0, src)]
2while heap:
3 d, u = heapq.heappop(heap)
4 if d > dist.get(u, inf): continue
5 for v, w in graph[u]:
6 if d + w < dist.get(v, inf):
7 dist[v] = d + w; heapq.heappush(heap, (d + w, v))

Complexity: time O((V + E) log V), space O(V + E)

O((V + E) log V) with a binary heap. BFS only if all weights are equal. Floyd-Warshall O(V³) for all pairs on dense graphs. Negative edges → Bellman-Ford O(VE).

Read the walkthrough as text

Classic diamond. Nodes A,B,C,D with edges A→B:1, A→C:4, B→C:2, B→D:5, C→D:1. Source A.

  1. Dist: A0, others ∞. Pop A; relax B→1, C→4.
  2. Pop B (dist 1); relax C→min(4,1+2)=3, D→6.
  3. Pop C (dist 3); relax D→min(6,3+1)=4.
  4. Pop D with 4, final. Path A-B-C-D.

Never re-process a node after it was popped with its best distance.

3Recognise it

Kinds of problems (5)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Single-source shortest paths

    Example. Dijkstra from source s to all nodes with non-negative weights.

    How. Min-heap (dist, node); relax neighbours when d+w improves; skip stale pops.

  • Minimum effort / bottleneck path

    Example. Minimise maximum edge weight on a path.

    How. Dijkstra on max edge so far, or union-find on sorted edges until connected.

  • Shortest path with at most k stops (Bellman-Ford style)

    Example. Cheapest flight with ≤ k layovers.

    How. Relax all edges for k+1 rounds, or DP[stops][v] from previous layer.

  • Shortest path on a weighted grid

    Example. Minimum effort path in a grid of heights.

    How. Dijkstra with 4-neighbour moves and effort = max step height difference.

  • All-pairs shortest paths (Floyd–Warshall)

    Example. Min distance between every pair of nodes.

    How. Triple loop: for each via k, relax dist[i][j] through k; k is outermost.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Stale entries processed

    Why it happens. Old (dist, node) pairs look harmless if you still relax edges.

    How it fails. Pop (5, u) when dist[u] already 3, redundant relaxations explode queue size.

    Fix. On pop: `if d > dist[u]: continue` before relaxing neighbours.

  • BFS on weighted graph

    Why it happens. BFS found shortest paths on unweighted grids before.

    How it fails. Weights 1 and 10: BFS treats both as one step, path cost 2 instead of 11.

    Fix. Non-uniform weights need Dijkstra (or Bellman-Ford if negatives).

  • Negative weights

    Why it happens. Dijkstra is the default “shortest path” algorithm.

    How it fails. Edge weight −5 makes Dijkstra pick wrong order, distances never corrected.

    Fix. Negative weights → Bellman-Ford or SPFA; not plain Dijkstra.

  • Intermediate node in the inner loop

    Why it happens. Nested i,j inside k still visits all triples.

    How it fails. k innermost: paths using intermediate high-index nodes never considered in later k.

    Fix. Floyd-Warshall: k (intermediate) is the outer loop, then i, j.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons