Shortest Path in an Unweighted Graph: BFS With Parent Pointers

"Find the shortest path from start to goal" sounds like a job for Dijkstra's algorithm. When every edge costs the same, it is not. Plain breadth-first search already finds the path with the fewest edges, and one extra dictionary turns the distance it discovers into the route itself.

The problem it solves

Given a graph whose edges all have the same cost, find a path from start to goal using as few edges as possible, or report that there is none. The same question hides in many costumes:

• the fewest knight moves between two squares,
• the fewest single-letter changes from one word to another,
• the fewest steps through a maze of open and blocked cells,
• the fewest hops between two people in a social graph.

Depth-first search finds a path, but not necessarily a short one: it commits to one branch and follows it to the end. Trying every path and keeping the shortest is correct, but the number of paths can grow exponentially.

The intuition

BFS explores in rings. First the start, then everything one edge away, then everything two edges away, and so on. A queue enforces this: nodes come out in the order they went in, so no node at distance d + 1 is processed before every node at distance d.

That gives the key fact: the first time BFS reaches a node, it has reached it by a shortest path. Any shorter route would have belonged to an earlier ring and been found earlier.

The distance is therefore free. To get the route, record who discovered each node, parent[node], at the moment it is first reached. When the goal comes out of the queue, follow the parents back to the start and reverse the list. Only the first discovery is ever recorded, so the trail always follows shortest paths.

Watch it run

The animation uses the lesson's knight graph. BFS leaves a1, discovers b3 and c2, and writes parent[b3] = a1 and parent[c2] = a1. No frame ever writes a parent for d4 from c2: by the time c2 is expanded, d4 already has its parent, b3. After the queue empties, the trail is walked back from c6 to a1 and reversed into ['a1', 'b3', 'd4', 'c6'].

The code

BFS with a parent dictionary. The dictionary is also the visited set, and the search stops as soon as the goal is dequeued:

from collections import deque

def shortest_path(graph, start, goal):
    parent = {start: None}                 # doubles as the visited set
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:        # walk the trail back to start
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nb in graph.get(node, []):
            if nb not in parent:           # mark when ENQUEUED, not dequeued
                parent[nb] = node
                queue.append(nb)
    return None                            # goal unreachable

g = {"a1": ["b3", "c2"], "b3": ["a1", "d4"], "c2": ["a1", "d4"],
     "d4": ["b3", "c6"], "c6": ["d4"]}
print(shortest_path(g, "a1", "c6"))                                   # ['a1', 'b3', 'd4', 'c6']
print(shortest_path(g, "a1", "a1"), shortest_path(g, "c6", "zz"))     # ['a1'] None

On a grid, the graph is implicit: each open cell's neighbours are the open cells above, below, left and right. Storing a distance instead of a parent is enough when only the length is asked for:

def grid_path_length(grid, start, goal):
    """Fewest moves through '.' cells, 4 directions; -1 if unreachable."""
    rows, cols = len(grid), len(grid[0])
    dist = {start: 0}
    queue = deque([start])
    while queue:
        r, c = queue.popleft()
        if (r, c) == goal:
            return dist[(r, c)]
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "." \
                    and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(r, c)] + 1
                queue.append((nr, nc))
    return -1

maze = ["..#.",
        ".##.",
        "....",
        "#.#."]
print(grid_path_length(maze, (0, 0), (0, 3)), grid_path_length(maze, (0, 0), (3, 1)))
# 7 4

BFS against a brute force that enumerates every simple path by depth-first search, on 1,000 random directed graphs. The check also confirms that each returned path starts and ends in the right place and uses only real edges:

import random

def all_simple_path_lengths(graph, start, goal):
    """Brute force: every simple path by DFS, return the edge counts."""
    lengths, seen = [], {start}
    def dfs(node, depth):
        if node == goal:
            lengths.append(depth)
            return
        for nb in graph.get(node, []):
            if nb not in seen:
                seen.add(nb)
                dfs(nb, depth + 1)
                seen.remove(nb)
    dfs(start, 0)
    return lengths

random.seed(21)
ok = True
for _ in range(1000):
    n = random.randint(1, 8)
    graph = {v: [] for v in range(n)}
    for u in range(n):
        for v in range(n):
            if u != v and random.random() < 0.3:
                graph[u].append(v)                  # directed edges
    s, t = random.randrange(n), random.randrange(n)
    path = shortest_path(graph, s, t)
    lengths = all_simple_path_lengths(graph, s, t)
    if path is None:
        ok &= lengths == []
    else:
        ok &= path[0] == s and path[-1] == t
        ok &= all(b in graph[a] for a, b in zip(path, path[1:]))   # real edges
        ok &= len(path) - 1 == min(lengths)
print(ok)                                                             # True

The complexity

• Time is O(V + E): each node is enqueued at most once, and each adjacency list is scanned once when its node is dequeued. On an R × C grid that is O(R * C), since each cell has at most four neighbours.
• Space is O(V) for the queue and the parent dictionary.
• Rebuilding the path costs O(length of the path), which is at most V.

Where it goes wrong

• Marking visited on dequeue. If a node is marked only when it leaves the queue, several neighbours can enqueue it before that happens. With a skip-if-visited check on dequeue the answer can still be right, but the queue holds duplicate copies that cost time and memory, and a parent written by a later copy can replace the first one. Mark on enqueue.
• Using DFS. Depth-first order does not produce rings, so the first path found says nothing about the shortest one.
• Forgetting to reverse. The trail runs from goal to start.
• Weighted edges. BFS counts edges, not cost. As soon as edges have different weights, use Dijkstra's algorithm.
• Blocked start or goal. In the grid version the start is enqueued without checking its own cell. Decide whether a start on a wall is an error, and check it before the loop.

How to say it in an interview

"On an unweighted graph BFS explores in order of distance, so the first time it reaches a node, it got there by a shortest path. I keep a parent map, which also serves as the visited set, and write a node's parent when I first enqueue it. When the goal comes off the queue, I follow parents back to the start and reverse. That's O(V + E) time and O(V) space. If edges had weights I'd switch to Dijkstra; if there were many start points, I'd seed the queue with all of them at distance zero."

The traversal itself is walked through in BFS explained, and seeding one queue with many sources is multi-source BFS.