Shortest path: what breadth-first search would have done

And it came to pass, when Pharaoh had let the people go, that God led them not through the way of the land of the Philistines, although that was near; for God said, Lest peradventure the people repent when they see war, and they return to Egypt: but God led the people about, through the way of the wilderness of the Red sea. — Exodus 13:17–18 (KJV)

When Israel left Egypt, there was a short, well-travelled road to Canaan along the Mediterranean coast. Scripture says plainly that it was near — and that God didn’t take it. He led them the long way, through the wilderness.

Let’s first see how a computer finds the short road, and then ask what it missed.

The map as a graph

Turn the land into a grid of squares. Some squares are open, some are mountains or sea. From any open square you can step to its neighbours: up, down, left, right. Programmers call this a graph: squares are nodes, and each possible step is an edge.

The question: what is the fewest number of steps from Egypt to Canaan?

Breadth-first search: spread out like a ripple

Breadth-first search (BFS) answers that by exploring in rings:

1. Start at Egypt (0 steps).
2. Visit every square 1 step away.
3. Then every square 2 steps away, then 3, and so on.

The first time the ripple touches Canaan, you’ve found the shortest route, because every shorter distance was already explored.

The trick that keeps the ripple in order is a queue: first in, first out. Squares are added to the back and taken from the front, so all the 1-step squares are handled before any 2-step square.

The code

from collections import deque

def bfs(start, goal, neighbors):
    queue = deque([start])
    parent = {start: None}            # how we reached each square (and "seen")
    while queue:
        node = queue.popleft()        # oldest discovery first
        if node == goal:
            break
        for nb in neighbors(node):
            if nb not in parent:      # never visit a square twice
                parent[nb] = node
                queue.append(nb)

    if goal not in parent:
        return None                   # no road at all
    # walk the parents back from Canaan to Egypt
    path, node = [], goal
    while node is not None:
        path.append(node)
        node = parent.get(node)
    return path[::-1]

Each square is added to the queue at most once, and each step between squares is looked at once, so BFS runs in O(V + E) time — the number of squares plus the number of connections.

function bfs(start, goal, neighbors) {
  const queue = [start];
  const parent = new Map([[start, null]]);
  for (let i = 0; i < queue.length; i++) {      // an index instead of shift() keeps it O(1)
    const node = queue[i];
    if (node === goal) break;
    for (const nb of neighbors(node)) {
      if (!parent.has(nb)) { parent.set(nb, node); queue.push(nb); }
    }
  }
  if (!parent.has(goal)) return null;          // no road at all
  const path = [];
  for (let n = goal; n != null; n = parent.get(n)) path.push(n);
  return path.reverse();
}

(In JavaScript, use string keys like "3,5" for grid squares: arrays aren’t equal to each other even with the same numbers.)

What “shortest” leaves out

BFS found the coastal road, and BFS is right: it is the fewest steps. But BFS only knows one thing about each step — that it’s a step. It has no idea that the coast road ran through Philistine land, or that a people fresh out of slavery might see war and turn back.

In programming terms, BFS treats every edge as costing the same. Real problems rarely do. When some steps cost more — time, danger, money — you give each edge a weight and use an algorithm like Dijkstra’s that finds the cheapest path instead of the shortest one. Change what you measure, and “the best path” changes with it.

God measured something the map couldn’t show.

Common mistakes

• Using a stack instead of a queue. Take from the back and you get depth-first search: it finds a path, not the shortest one.
• Marking squares as seen too late. Mark a square when you add it to the queue (as above), not when you take it out, or it can be added many times.
• list.pop(0) in Python. It shifts the whole list every time. Use collections.deque and popleft().

Try it

1. Write neighbors(node) for a grid given as a list of strings, where # is a wall:

   MAP = ["S..#....",
          ".#.#.##.",
          ".#...#..",
          "...#...G"]

2. Change the code to return the number of steps only, using a distance dictionary instead of parent.
3. Swap the queue for a stack (pop() instead of popleft()). Is the path still the shortest?

Reflect

“The shortest path isn’t always the best one.” The long way through the wilderness was where Israel learned to trust — manna each morning, water from the rock, a pillar of cloud by day and fire by night (Exodus 13:21).