BFS on Unweighted Graphs

When every edge has the same weight, the shortest path is the path with the fewest edges. That’s exactly what BFS finds — for free, in the order it visits vertices.

This is the smallest, fastest, and easiest case to get right. If a problem fits, don’t overthink it.

Why BFS gives you shortest paths

BFS explores the graph in layers. Layer 0 is the source. Layer 1 is every vertex one edge away. Layer 2 is every vertex two edges away (and not already in layer 0 or 1). And so on.

The first time BFS visits vertex v, it does so via the shortest possible number of edges. Why? Because if there were a shorter route, BFS would have reached v in an earlier layer (it processes layer k completely before touching layer k + 1).

This is only true because every edge has the same cost. As soon as one edge is “cheaper” than another, BFS layers no longer correspond to shortest distances, and you need Dijkstra.

BFS from A — layers reveal shortest distances

6 nodes · 7 edges

step 0/6

The template

Time: O(V + E). Space: O(V) for the distance array and queue.

The dist == -1 check is doing double duty as both “visited?” and “what’s the distance?”. One array, two purposes.

Grid problems — the most common BFS shortest path

A massive fraction of “shortest path” interview problems are actually BFS on a grid:

Given an m × n grid with some cells passable and some blocked, find the shortest path from (0, 0) to (m - 1, n - 1) moving 4-directionally.

The graph is implicit — vertices are cells, edges go to the four neighbors. Build adjacency on the fly.

Multi-source BFS

What if you need shortest distance to the nearest of several sources? “From every land cell, what’s the distance to the nearest water cell?”

Run BFS from all sources at once. Initialize the queue with every source at distance 0, then BFS exactly as before. The first time a vertex is visited, it’s visited by its nearest source.

This pattern shows up in Rotting Oranges, Walls and Gates, 01 Matrix, Shortest Bridge, and more. Multi-source BFS is the single most useful BFS technique outside the basic version.

0-1 BFS

What if edge weights are only 0 or 1? You don’t need Dijkstra’s full O((V + E) log V) — there’s a clean middle ground.

Use a deque instead of a queue. When relaxing an edge with weight 0, push to the front. When relaxing weight 1, push to the back. The deque automatically processes 0-weight neighbors first, so vertices come out in order of distance.

from collections import deque
 
def bfs_01(n, adj, src):
    # adj[u] = list of (v, weight in {0, 1})
    dist = [float('inf')] * n
    dist[src] = 0
    dq = deque([src])
    while dq:
        u = dq.popleft()
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if w == 0:
                    dq.appendleft(v)
                else:
                    dq.append(v)
    return dist

Time: O(V + E). Useful for grid problems where some moves are “free” and others cost 1 (rotating cells, knight moves with a special discount, etc.).

When BFS is NOT the answer

Edges have different positive weights. Use Dijkstra.
Negative edges exist. Use Bellman-Ford.
You need all-pairs distances and V ≤ 400. Floyd-Warshall is simpler than V BFS calls when there’s also weights.
The “graph” is enormous and only the target matters. Consider bidirectional BFS — start from both source and target simultaneously and meet in the middle. Roughly square-roots the explored frontier.

Quick check

In an unweighted graph, why does BFS from source s give the shortest distance to every vertex?

What's the time complexity of multi-source BFS with K sources on a graph with V vertices and E edges?

Next: when edges have different weights, Dijkstra’s algorithm takes over.

Introduction Dijkstra's Algorithm