BFS Shortest Path

BFS shortest path finds the minimum number of edges from a start vertex to other vertices in an unweighted graph.

It works because BFS visits vertices in increasing distance from the start.

Core Idea

When every edge has the same cost, the first time BFS discovers a vertex is through a shortest path to that vertex.

The algorithm stores a distance for each discovered vertex and increases the distance by one when moving to a neighbor.

Python Example

from collections import deque
 
def bfs_distances(graph, start):
    distance = {start: 0}
    queue = deque([start])
 
    while queue:
        node = queue.popleft()
 
        for neighbor in graph[node]:
            if neighbor not in distance:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
 
    return distance

The distance dictionary also acts as a visited record.

Common Confusions

BFS shortest path means shortest by edge count, not smallest total weight.

If edges have different weights, ordinary BFS is not enough unless the weights have special structure.

When To Use It

Use BFS shortest path for unweighted graphs, grids with equal-cost moves, minimum number of moves, and shortest transformation sequences where each step costs one.