Dijkstra's Algorithm: Shortest Paths with a Priority Queue

Why This Matters

Dijkstra's algorithm is the standard tool for shortest paths when edge weights are nonnegative. It appears in routing, maps, network latency, game pathfinding, dependency cost planning, and recommendation graph traversal.

It is also the page where priority queues become obviously necessary.

Core Idea

Maintain the best-known distance from the source to every vertex. Repeatedly settle the unsettled vertex with smallest distance, then relax its outgoing edges.

dist[source] = 0
push(source, 0)
while priority queue is not empty:
  v, d = pop_min()
  if d is stale: continue
  for each edge v -> u with weight w:
    if d + w < dist[u]:
      dist[u] = d + w
      push(u, dist[u])

With a binary heap, the common implementation is O((V + E) log V).

Non-Example or Failure Mode

Dijkstra's algorithm is not correct with negative edge weights. A later negative edge can improve a vertex after it has already been settled.

Use Bellman-Ford when negative weights are allowed and negative cycles must be detected.

Worked Example

Edges: A -> B cost 4, A -> C cost 1, C -> B cost 2, B -> D cost 1, C -> D cost 5.

Start at A.

dist[A] = 0; relax A: B = 4, C = 1.
Pop C because 1 is smallest; relax C: B = 3, D = 6.
Pop B; relax B: D = 4.
Pop D; shortest distance from A to D is 4.

The shortest route is A -> C -> B -> D.

Common Mistakes

Mistake	Correction
Using Dijkstra with negative edges.	Use Bellman-Ford or reweighting techniques when negatives exist.
Marking vertices visited when first discovered.	Settle them when popped with smallest non-stale distance.
Forgetting stale priority queue entries.	Skip a popped pair if its distance is not current.
Confusing BFS with Dijkstra.	BFS is for unweighted or equal-weight edges.

Diagnostic Questions

Question type	Question	Answer signal
Definition	What problem does Dijkstra solve?	Single-source shortest paths with nonnegative weights.
Example / non-example	Can it handle an edge of weight `-2`?	No, not in its standard form.
Computation	Why does the priority queue order by distance?	The smallest tentative distance is the next safe vertex to settle.
Proof	What invariant drives correctness?	Settled vertices have final shortest distances.
Transfer	Why is it useful for latency-aware routing?	Edge weights can represent latency or cost.

Exercises

Beginner:

Run Dijkstra by hand on a four-node weighted graph.
Explain why BFS fails when edge weights differ.
Identify which vertex is popped next from a list of tentative distances.

Intermediate:

Implement Dijkstra with lazy duplicate priority queue entries.
Add predecessor tracking to reconstruct the shortest path.

Challenge:

Compare Dijkstra, Bellman-Ford, and A* on the same grid or road graph.

Diagram Recommendation

Type: shortest-path frontier trace.

Caption: "Dijkstra settling vertices in increasing distance order."

Purpose: Show relaxation, stale entries, and the priority queue frontier.

Next Topics

References

Dijkstra, E. W. "A note on two problems in connexion with graphs." 1959.
Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 22.
MIT OpenCourseWare. 6.006 Introduction to Algorithms, shortest paths material.