Skip to content
BytePatterns

Shortest Path, Unweighted

Graphs: lesson 6 of 8

BFS already found it — store parents to read it back.

Lesson 6 of 8 · 6 min

Shortest Path, Unweighted

Step 1 of 11

Every move costs the same, so the first time BFS touches a square it has arrived by the fewest hops.

The Idea

Every edge costs the same, so the first time BFS touches a node it has arrived by the fewest possible hops. The distance is free. To recover the route itself, record which node discovered each one, then follow those parent links back from the goal and reverse.

Real-World Example

Asking how few knight moves get from one corner of a chessboard to the other. Every knight move counts the same, so the answer is a hop count, and the useful output is not the number but the actual sequence of squares — which only the parent trail can give you.

The Code

from collections import deque
g = {"a1": ["b3", "c2"], "b3": ["a1", "d4"], "c2": ["a1", "d4"],
     "d4": ["b3", "c6"], "c6": ["d4"]}
parent, q = {"a1": None}, deque(["a1"])
while q:
    n = q.popleft()
    for m in g[n]:
        if m not in parent:
            parent[m] = n                # who reached m first
            q.append(m)
node, path = "c6", []
while node:                              # walk the trail backwards
    path.append(node)
    node = parent[node]
print(path[::-1])   # ['a1', 'b3', 'd4', 'c6']

Your turn

Put the steps in the right order.

  1. Reverse the collected list so it reads start to goal
  2. Put the start node in the queue with no parent
  3. Walk back from the goal, following parent links
  4. Expand the queue, recording a parent each time a node is first seen

Mini quiz

1 / 3

On an unweighted graph, BFS finds: