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.

The condition “every edge has the same cost” is essential. BFS is not comparing total weights. It is counting layers.

Function Contract

bfs_distances(graph, start) expects an unweighted adjacency list and a start vertex that appears as a key in graph.

It returns a dictionary where distance[node] is the minimum number of edges from start to node. Vertices not reached from start do not appear in the dictionary.

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.

Step-by-Step Example

If A connects to B and C, and B connects to D, BFS from A discovers:

A: distance 0
B, C: distance 1
D: distance 2

D is first discovered through B, and that path has two edges. BFS cannot later find a one-edge path to D, because all one-edge neighbors were processed before distance-two vertices.

Why It Works

The queue processes vertices by discovery layer. All vertices at distance k are removed from the queue before vertices at distance k + 1 are processed. Therefore, when a vertex is first discovered, the path used to discover it has the fewest possible number of edges.

The visited record is safe because a later discovery would be at the same or greater distance.

Complexity

With an adjacency list, BFS shortest path is O(V + E). The distance dictionary and queue use O(V) space.

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.

Another common mistake is marking distance only after popping. Marking when enqueuing avoids putting the same vertex into the queue many times.

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.

Do not use ordinary BFS for weighted shortest path problems unless all weights are equal or the problem has a special structure designed for BFS.

The Main Point

BFS shortest path is about minimum edge count in an unweighted graph. Equal edge cost is the condition that makes first discovery final.