M3-T2 — Breadth-First Search and Dijkstra

Learning objectives

After this lesson, you should be able to:

• Run breadth-first search and Dijkstra by hand on a small graph and record the queue.
• State why a priority queue gives shortest paths when step costs are not negative.
• Explain why a node is final when it is popped and not when it is first reached.
• Give the running time of each method and say what a negative cost breaks.

The intuition

Picture a drop of ink spreading through the corridors of the hospital. After one step it has reached the neighbouring cells, after two steps their neighbours, and so on. If every step takes the same time, the ink reaches each cell exactly when the shortest route to it would. That is breadth-first search: it expands in rings of equal step count.

Now suppose the ink moves faster over polished floor and slower through the crowded waiting room. The first place the ink arrives at is no longer the nearest by steps but the nearest by time. Dijkstra's algorithm is the same ink with the clock running: it always expands the place the ink would reach next. The result, for every place, is the time at which the ink first arrives and the neighbour it came from, and following those neighbours back from the goal is the cheapest route.

The mathematics

Breadth-first search

Keep a first-in first-out queue. Take the oldest cell, add every unvisited neighbour to the back, and remember where each came from. Each cell enters the queue once, so the time is proportional to the cells and edges.

BFS(start):
  queue ← [start];  seen ← {start}
  while queue not empty:
    u ← pop front
    for each neighbour v of u not in seen:
      seen ← seen ∪ {v};  parent[v] ← u;  push v at the back

When every step costs the same, BFS finds a path with the fewest steps, and so the cheapest. When costs differ it does not.

Dijkstra's algorithm

Keep for every node a tentative cost d, the best cost found so far, and a priority queue ordered by d. Repeatedly take the node with the smallest d, declare it final, and relax its edges: if going through it gives a neighbour a lower cost, update that cost and parent.

Dijkstra(start):
  d[start] ← 0;  d[other] ← ∞;  queue ← {(0, start)}
  while queue not empty:
    (du, u) ← pop smallest
    if du > d[u]: continue            # a stale entry
    if u is the goal: stop
    for each edge (u, v) with cost c ≥ 0:
      if d[u] + c < d[v]:
        d[v] ← d[u] + c;  parent[v] ← u;  push (d[v], v)

d[v]

the best known cost from the start to v. It only ever decreases, and it is exact once v has been popped.

parent[v]

the node from which d[v] was achieved. Following parents back from the goal gives the route.

stale entry

a queue entry whose cost is higher than the current d[v]: the node was found again more cheaply. It is skipped rather than removed (lazy deletion).

Why it works

The key fact is an invariant: when a node u is popped, d[u] is the true shortest cost. Suppose not. Then the true shortest path to u leaves the set of finished nodes through some edge from a finished node x to an unfinished node y, with y still in the queue. Because d[y] ≤ d[x] + c(x, y) was set when x was finished, and costs are not negative, d[y] is no more than the true cost to u, and so it is no more than d[u]. But u was popped instead of y, so d[u] ≤ d[y]. Hence d[u] equals the true cost. The argument breaks if any c is negative, because the path beyond y could then be cheaper than y.

Running time

For a grid, E is about 2 to 4 times V, so Dijkstra with a heap is about O(V log V). Searching the whole floor of lesson M3-T1 (240,000 cells) takes a fraction of a second; with a goal in view, the search stops when the goal is popped, which is usually much earlier.

A worked example

Six places. Scout is at S and the pharmacy is G. The graph is the one in the figure. Costs: S–A 4, S–B 1, B–A 2, A–C 5, B–C 8, C–G 3, A–D 10, D–G 2.

pop S (0)    relax A = 4, B = 1
pop B (1)    relax A = 3 (was 4), C = 9
pop A (3)    relax C = 8 (was 9), D = 13
  skip stale A (4)
pop C (8)    relax G = 11
  skip stale C (9)
pop G (11)   goal reached: stop

Follow the parents back from G: G ← C ← A ← B ← S. The route S, B, A, C, G costs 1 + 2 + 5 + 3 = 11. Two things are worth noticing. First, A was reached first by the direct edge from S at cost 4, and a moment later through B at cost 3: marking A final when it was first discovered would have given the wrong answer. Second, D, with d = 13, was never expanded, because G was popped before it.

Breadth-first on the same graph. BFS reaches G in three edges, S, A, C, G, at cost 4 + 5 + 3 = 12. It is the route with the fewest edges and it is one unit worse than the cheapest, because it never looked at costs. On a hospital grid the same effect is a route through the crowded waiting room: fewest steps, highest cost (lab M3-L1).

The cost of a lazy queue. The trace pushed 8 entries (S, A, B, A, C, C, D, G) and popped 5 nodes plus 2 stale entries, leaving D unexpanded. With lazy deletion the queue can hold up to E entries instead of V, and that is a good trade: no heap needs a “decrease key” operation.

Engineering implications and limitations

Stop at the goal

For a single goal, stop when it is popped. Stopping when it is first pushed returns a route that may be too expensive; the goal's cost can still fall while it waits in the queue (lab M3-L1, stage 2).

One search, many answers

A search from the start gives the cost to every cell, so the nearest of several goals comes from one search that stops at the first goal popped. Run backwards from the goal it gives a cost-to-go field for every possible robot position, which the replanning lessons build on (lesson M3-T6).

Ties

Many routes can have the same cost. Which one the search returns depends on how ties are broken in the queue, so tests should compare costs and validity, not exact routes.

When Dijkstra is the right tool

Dijkstra has no heuristic, so it spreads evenly in every direction. That is wasteful for one goal on a large map, and ideal when you need distances to many places, for example a cost map from a charging dock, a distance field, or a map of how far every room is from the pharmacy. For a single goal, A* (lesson M3-T3) does the same work with fewer expansions.

Floating point costs

With diagonal costs of √2 the totals are not exact. Compare costs with a tolerance, and do not use floating point equality to decide whether a cell has improved by a tiny amount: use a strict improvement test.

Common misconceptions

Engineering takeaways

1. Breadth-first search expands in rings of equal step count and minimises steps; Dijkstra expands in order of cost and minimises cost.
2. Dijkstra keeps a best-known cost and parent per node, and relaxes edges of the node it pops.
3. A node is final when it is popped; this holds only if no step cost is negative.
4. With a binary heap Dijkstra runs in O((V + E) log V); stopping at the goal usually saves most of it.
5. One search from the start yields costs to all nodes, and one backwards from the goal yields a cost-to-go for every start.

References and further reading

The original paper and the standard textbook treatments.

• E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik, 1, 269-271, 1959.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, MIT Press, chapter on single-source shortest paths.
• S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed., Pearson, 2020, chapter 3 (breadth-first and uniform-cost search).

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: A*, which adds an estimate of the distance still to go so the search leans towards the goal.

Related content

Nothing below is required to finish this lesson.

• Before
  M3-T1: Search Problems on Grids and Graphs

  Define a search problem (states, actions, costs, goal) and compare 4- and 8-connected grids.

• Lab
  M3-L1: Implement Dijkstra

  Scout needs the cheapest route to the pharmacy: implement Dijkstra on the hospital grid.