Breadth-first search by distance

When to use it

Use it when the question is the fewest steps from a start, or from several starts at once, and every step costs the same: places are reached nearest first.

It belongs to the graphs group: Visit every place you can reach, once each, in the order that suits the question.

Watch it work

A metro map lists its lines: each line joins two stations, and trains run both ways. One ride takes you along one line. Return the fewest rides from the start station to the goal station, or -1 if no route exists.

Input
links = [["Ash", "Bay"], ["Ash", "Cove"], ["Bay", "Dock"], ["Cove", "Dock"], ["Cove", "Elm"], ["Dock", "Fort"], ["Elm", "Fort"], ["Fort", "Glen"]]
start = "Ash"
goal = "Fort"

Output
3

The method

1. List the neighbors of every station, each line both ways
2. Start a queue with the start station, which is 0 rides away
3. Take the station at the front of the queue
4. If it is the goal, stop: its number of rides is final
5. A neighbor with no number is one ride farther: queue it
6. Return the goal's number of rides, or -1 if it has none

The run, one moment at a time

1. Step 1. The map has 7 stations and 8 lines. Each line is listed for both of its stations, so Ash has Bay and Cove as neighbors. No station has a number of rides yet.

   queue: empty
   station: Ash Bay Cove Dock Elm Fort Glen
   rides: ? ? ? ? ? ? ?
   

2. Step 2. Ash is the start, so it is 0 rides away. It waits in the queue. A "?" means a station that has not been reached.

   queue: Ash  (front at 0)
   station: Ash Bay Cove Dock Elm Fort Glen
   rides: 0 ? ? ? ? ? ?
   

3. Step 5. Take Ash from the front: 0 rides. Bay and Cove have no number yet: each gets 0 + 1 = 1 and they join the back of the queue.

   queue: Bay Cove  (front at 0)
   station: Ash Bay Cove Dock Elm Fort Glen
   rides: 0 1 1 ? ? ? ?
   

4. Step 5. Take Bay from the front: 1 ride. Ash has a number already. Dock has no number yet: it gets 1 + 1 = 2 and joins the back.

   queue: Cove Dock  (front at 0)
   station: Ash Bay Cove Dock Elm Fort Glen
   rides: 0 1 1 2 ? ? ?
   

5. Step 5. Take Cove from the front: 1 ride. Ash and Dock have numbers already. Elm has no number yet: it gets 1 + 1 = 2 and joins the back.

   queue: Dock Elm  (front at 0)
   station: Ash Bay Cove Dock Elm Fort Glen
   rides: 0 1 1 2 2 ? ?
   

6. Step 5. Take Dock from the front: 2 rides. All stations 1 ride away were handled before it. Bay and Cove have numbers already. Fort has no number yet: it gets 2 + 1 = 3 and joins the back.

   queue: Elm Fort  (front at 0)
   station: Ash Bay Cove Dock Elm Fort Glen
   rides: 0 1 1 2 2 3 ?
   

7. Step 3. Take Elm from the front: 2 rides. Cove and Fort have numbers already, and the first number a station gets is its fewest. Nothing joins the queue.

   queue: Fort  (front at 0)
   station: Ash Bay Cove Dock Elm Fort Glen
   rides: 0 1 1 2 2 3 ?
   

8. Step 4. Take Fort from the front. It is the goal, so the search stops here. Glen was never reached, and it does not need to be.

   queue: empty
   station: Ash Bay Cove Dock Elm Fort Glen
   rides: 0 1 1 2 2 3 ?
   

9. Step 6. Fort got its number the first time it was reached, and every nearer station was handled before it. The fewest rides from Ash to Fort is 3.

   queue: empty
   station: Ash Bay Cove Dock Elm Fort Glen
   rides: 0 1 1 2 2 3 ?
   

The code

The numbered comments are the steps of the method.

function solve(links, start, goal) {
  // 1. List the neighbors of every station, each line both ways
  const nearby = new Map();
  for (const [a, b] of links) {
    if (!nearby.has(a)) nearby.set(a, []);
    if (!nearby.has(b)) nearby.set(b, []);
    nearby.get(a).push(b);
    nearby.get(b).push(a);
  }
  // 2. Start a queue with the start station, which is 0 rides away
  // rides maps a station to its number. A station with a number has
  // been reached, so rides is also the record of what was seen.
  const rides = new Map([[start, 0]]);
  // Taking from the front of an array is slow, so nothing is removed:
  // head is the position of the front.
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    // 3. Take the station at the front of the queue
    const station = queue[head];
    // 4. If it is the goal, stop: its number of rides is final
    if (station === goal) break;
    // 5. A neighbor with no number is one ride farther: queue it
    for (const other of nearby.get(station) ?? []) {
      if (rides.has(other)) continue;
      rides.set(other, rides.get(station) + 1);
      queue.push(other);
    }
  }
  // 6. Return the goal's number of rides, or -1 if it has none
  return rides.has(goal) ? rides.get(goal) : -1;
}

from collections import deque

def solve(links, start, goal):
    # 1. List the neighbors of every station, each line both ways
    nearby = {}
    for a, b in links:
        if a not in nearby:
            nearby[a] = []
        if b not in nearby:
            nearby[b] = []
        nearby[a].append(b)
        nearby[b].append(a)
    # 2. Start a queue with the start station, which is 0 rides away
    # rides maps a station to its number. A station with a number has
    # been reached, so rides is also the record of what was seen.
    rides = {start: 0}
    # A deque is fast at both ends: append adds at the back,
    # popleft takes from the front.
    queue = deque([start])
    while queue:
        # 3. Take the station at the front of the queue
        station = queue.popleft()
        # 4. If it is the goal, stop: its number of rides is final
        if station == goal:
            break
        # 5. A neighbor with no number is one ride farther: queue it
        for other in nearby.get(station, []):
            if other in rides:
                continue
            rides[other] = rides[station] + 1
            queue.append(other)
    # 6. Return the goal's number of rides, or -1 if it has none
    return rides[goal] if goal in rides else -1

How to spot it

Asked: The fewest steps, moves or changes to get from A to B

Places leave the queue in order of distance. The first time the target appears, no shorter way to it can exist.

Given: Something spreads to every neighbor once per minute or per day

After t rounds it has reached everything t steps from where it began. The time a place is reached is its distance.

Asked: The distance from each cell to the nearest of several sources

Put all the sources in the queue first, at distance 0. They spread together, and each cell is first reached from its nearest source.

Given: One move changes a single letter, digit or position

Each value is a place and each allowed change is a step to a neighbor. No list of links is given: you make the neighbors when you need them.

Looks like it, but is not

• Steps have different costs, such as roads of different lengths. Use Weighted shortest path. The fewest steps is then not the cheapest way. The first cost a place gets can be beaten later, so costs are improved until none changes.
• You only need to know whether a place can be reached, not how far away it is. Use Graph traversal with a visited set. No distance is asked, so the order of the visits does not matter. Any walk that marks what it reaches is enough.
• The fewest steps down from the root of a tree to some kind of node. Use Level-order tree traversal. It uses the same queue, but a tree never leads back to a node you have seen, so nothing needs a mark.

Cost and mistakes

Time grows with the places plus the links, written O(V + E) for V places and E links: each place joins the queue once, and each link is read from both ends. Extra space is the same, for the neighbor lists and the numbers.

Watch out

• Give a place its number when it joins the queue, not when it leaves. If you wait, the same place joins several times before it is marked, and a large input becomes very slow.
• Take from the front of the queue, never from the back. Taking the newest place first follows one path far away, and the first number a place gets may not be the fewest.

In the 150

3 problems of the 150 use it. Naming them gives their method away, so the list is folded.