Skip to content
Tutorials Center
My learning

Topics

Lesson 134 of 225 ยท Shortest Paths and Spanning Trees

Dijkstra's Algorithm

Learn Dijkstra's shortest path algorithm step by step: relaxation, a heapq version, path reconstruction, network delay time and why negative edges break it.

How does a map app find the fastest route? Roads have different lengths, so counting the number of road segments is not enough: two short roads may be slower than one long highway. Each road has a weight (distance or travel time), and you want the path whose total weight is smallest. Dijkstra's algorithm solves this for a graph whose weights are never negative. It is one of the most important algorithms in computer science, and it is the engine behind routing, network protocols and game pathfinding.

Breadth-first search already finds shortest paths when every edge counts as 1. Dijkstra is its big sibling: instead of a plain queue, it uses a priority queue so it always works on the vertex that is currently closest to the start.

The idea in one picture

Imagine pouring water at the start vertex. The water spreads along roads, taking longer on longer roads. The first time the water reaches a vertex is the shortest time to get there. Dijkstra simulates that.

TEXT
Roads (undirected, weight in brackets):
  A-B (4)   A-C (2)   B-C (1)   B-D (5)
  C-D (8)   C-E (10)  D-E (2)   D-F (6)   E-F (3)

Shortest distances from A:
  A=0   C=2   B=3 (through C: 2+1)   D=8 (through B)   E=10 (through D)   F=13 (through E)

The algorithm keeps a table dist[v], the best known distance from the start to v, starting at infinity except dist[start] = 0. Then it repeats:

  1. Pick the unfinished vertex u with the smallest dist.
  2. That distance is now final (we will see why in a moment).
  3. Relax every edge u -> v with weight w: if dist[u] + w < dist[v], we found a shorter way to v, so update dist[v].

Relaxation is the core step: "going through u is better than what I knew".

Why the greedy choice is safe

Suppose u is the unfinished vertex with the smallest tentative distance d. Could there be a shorter route to u? Any other route must leave the finished region through some other unfinished vertex x, and dist[x] >= d because u was the smallest. Since weights are not negative, adding more edges after x cannot make the route shorter than d. So d is final. This is exactly the step that breaks with negative weights, as you will see below.

Implementation with heapq

A simple way to always find the closest unfinished vertex is a min-heap of (distance, vertex) pairs, using Python's heapq. Python's heap has no "decrease key" operation, so we use lazy deletion: when we find a better distance, we push a new entry and leave the old one in the heap. When an old entry is popped later, its distance is larger than dist[v], so we skip it.

Python Dijkstra with heapq

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Unreachable vertices keep the distance inf. Tuples compare element by element, so entries with equal distance fall back to comparing vertex names; that is fine for strings but would fail for objects that cannot be compared. If your vertices are such objects, add a tie-breaking counter to the tuple.

Tracing the run

Let us watch the heap work on the same graph. Each line shows the entry we pop, whether it is stale, and what we relax.

Python Watching Dijkstra work

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You can see that B first gets distance 4 from A, then is improved to 3 through C, and the old (4, B) entry is skipped when it is popped. Every vertex is finalized exactly once, the first time a non-stale entry for it is popped.

Recovering the actual path

Distances are useful, but you usually want the route too. Keep a second dictionary prev: whenever you relax an edge into v from u, set prev[v] = u. To get the path, walk backwards from the target to the start and reverse.

Python Shortest path with route

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Stopping as soon as the goal is popped is valid, because a popped vertex is final. If you only need one target, this can save a lot of work. The cheapest route from A to F is 13, going through C, B, D and E; the direct-looking hop A to C to E costs 12 just to reach E, which is worse than the 10 you get by way of D.

Complexity

Each edge triggers at most one push, so the heap holds at most E entries, and each push or pop costs O(log E) = O(log V) (since E is at most V squared, log E is at most 2 log V). Every vertex's edges are scanned once when it is finalized. Total:

Version Time Space
Binary heap + adjacency list O((V + E) log V) O(V + E)
Plain array scan for the minimum O(V^2) O(V)
Fibonacci heap (theory) O(E + V log V) O(V)

The O(V^2) array version is actually better for dense graphs where E is close to V^2. For the sparse graphs of road maps and networks, the heap version wins.

Problem: network delay time

A network has n nodes numbered 1..n. Each triple [u, v, w] is a one-way link from u to v taking w time units to carry a signal. A signal starts at node k. How long until all nodes have received it? Return -1 if some node is never reached.

All nodes get the signal at the time of the shortest path to them, and the whole network is done when the slowest node has it. So: run Dijkstra from k, then take the maximum distance.

The brute force enumerates every path from k to every node. In a dense network the number of simple paths grows exponentially. Dijkstra needs O((V + E) log V).

Python Network delay time

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last case shows why the greedy approach pays off: the direct link to node 2 takes 5, but going through node 3 takes only 2.

Why negative edges break Dijkstra

The "this distance is final" argument assumed that extra edges can never reduce a path's length. A negative edge can. Look at this graph, where the edge B -> A has weight -5:

TEXT
        1         1
   S ------> A ------> C
   |         ^
 2 |         | -5
   +-------> B

Dijkstra finalizes A (distance 1) before it even looks at B (distance 2). Later, the route S, B, A costs 2 - 5 = -3, which is better, but A is already final and its neighbor C was computed from the old value. The true shortest distance to C is -2 (S, B, A, C), and an algorithm that finalizes each vertex once reports 2.

Python Dijkstra with a negative edge gives a wrong answer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first line reports C: 2, which is wrong, and the second reports the true -2. If a graph has negative edges, use Bellman-Ford, which is slower but correct (and can detect negative cycles). Some implementations that allow a vertex to be processed again do recover from negative edges, but they lose the guarantee of O((V + E) log V) and can loop forever on a negative cycle.

Common mistakes

  • Not skipping stale heap entries. Without if d > dist[u]: continue, the algorithm is still correct but may do a lot of repeated work.
  • Using it with negative weights. Check the input. A single negative edge invalidates the guarantee.
  • Treating inf as a number to add to. inf + 5 is still inf, which is fine, but with integer sentinels like 10**9 an overflow in other languages is a classic bug.
  • Forgetting directedness. For an undirected road, add the edge in both directions.
  • Using BFS for weighted graphs. BFS minimizes the number of edges, not the total weight.
  • Quitting too early. You may stop when the goal is popped, not when it is first pushed.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does Dijkstra's algorithm use a priority queue?

    The correctness argument relies on finalizing the closest unfinished vertex, and a min-heap finds it quickly.
  2. 2. What is the time complexity of Dijkstra with a binary heap and an adjacency list?

    Each edge causes at most one heap push, and each heap operation costs O(log V).
  3. 3. What does the check if d > dist[u]: continue do?

    Python's heapq has no decrease-key, so improved distances are pushed as new entries and the old ones are skipped when popped.
  4. 4. Why can a negative edge make Dijkstra give a wrong answer?

    The finalization argument needs extra edges to never shorten a path. With a negative edge, a longer-looking route can end up shorter than a finalized distance.
  5. 5. In a graph where every edge has weight 1, which simpler algorithm gives the same shortest distances?

    With equal weights, the number of edges is the distance, so a plain queue (BFS) already explores vertices in increasing distance order.

Summary

  • Dijkstra finds the shortest paths from one start vertex in a graph with non-negative edge weights.
  • It repeatedly finalizes the unfinished vertex with the smallest tentative distance and relaxes its outgoing edges.
  • With heapq and lazy deletion (skip entries where d > dist[u]) it runs in O((V + E) log V) time and O(V + E) space.
  • Record prev[v] on every successful relaxation to rebuild the actual route by walking backwards from the goal.
  • You can stop as soon as the goal is popped; run to the end for all distances (network delay time takes the maximum).
  • Negative edges break the finality argument; use Bellman-Ford instead. With all weights equal, plain BFS is enough.

Next: Bellman-Ford