BFS shortest path in an unweighted graph

Imagine you are standing at node 0 in a network and need to reach node 3 using the fewest possible hops. The graph has edges: $(0,1)$, $(0,2)$, $(1,3)$, and $(2,3)$. Without any direct edge between 0 and 3, you are faced with a choice of routes. If you blindly wander down the first path you find—say, heading deep into a hypothetical detour or stumbling across a circuitous route—you might waste precious steps before reaching your target.

In an unweighted graph, every edge costs the exact same amount: 1 hop. That means the shortest path is purely a matter of counting edges. But how do you guarantee you find the absolute minimum number of edges without manually tracing every single combination? If you try a depth-first exploration, you might wander down a long chain of vertices and return a path of length 3 or 4 while a shorter path of length 2 was sitting right next to your starting point.

This is precisely why we need Breadth-First Search (BFS). Instead of committing to one deep trail, BFS explores outward in expanding rings or layers, checking all neighbors at distance 1 before moving on to distance 2. For our network, exploring layer by layer ensures that the moment our search touches node 3, we have found a valid path of length 2 ($0\to 1\to 3$ or $0\to 2\to 3$) and can instantly stop without guessing.

To find the shortest path in our graph with edges (0, 1), (0, 2), (1, 3), and (2, 3) starting from node 0, we can visualize Breadth-First Search as an expanding ripple of water in a pond. Each step of the ripple corresponds to traversing exactly one edge. Node 0 is at the center (distance 0). Its immediate neighbors, nodes 1 and 2, form the first ripple ring at distance 1. When the ripple expands outward from that ring, it hits node 3 at distance 2.

Unlike depth-first search, which tumbles blindly down a single branch (such as 0 to 1 to 3 and potentially missing a shorter route, or wandering off into loops), BFS guarantees that we explore every node at distance $k$ before looking at any node at distance $k+1$. Because every edge in an unweighted graph carries the exact same "cost" (one hop), the very first time our search wave touches target node 3, we are 100% certain we have found a minimum-edge route.

Distance 0: [0]
Distance 1: ├── [1]
└── [2]
Distance 2: └── [3] (Reached via 0->1->3 or 0->2->3)

To manage this expanding wave mechanically, BFS uses a First-In, First-Out (FIFO) queue data structure. The queue ensures that nodes discovered earlier are always processed before nodes discovered later, perfectly enforcing our layer-by-layer expansion rule.

To see how the layer-by-layer ripple model functions in practice, let us trace our locked example graph: four nodes $\{0,1,2,3\}$ connected by undirected edges $\{(0,1),(0,2),(1,3),(2,3)\}$. We want to find the shortest path from start node 0 to target node 3. We maintain two core data structures: a FIFO queue for visiting nodes in order of discovery, and a distance map dist to record the shortest known hops from the start.

Given

- Graph nodes: $\{0,1,2,3\}$
- Graph edges: (0, 1), (0, 2), (1, 3), (2, 3)
- Start node: 0
- Target node: 3

Steps

1. Initialization: Set dist[0] = 0, and set dist for all other nodes to infinity (inf). Push start node 0 into the queue.
- queue = [0]
- dist = {0: 0, 1: inf, 2: inf, 3: inf}

2. Pop Node 0: Remove 0 from the front of the queue. Inspect its unvisited neighbors 1 and 2. Since their current distance is inf, update them: dist[1] = dist[0] + 1 = 1 and dist[2] = dist[0] + 1 = 1. Push 1 and 2 into the queue.
- queue = [1, 2]
- dist = {0: 0, 1: 1, 2: 1, 3: inf}

3. Pop Node 1: Remove 1 from the queue. Inspect its unvisited neighbors. Node 0 is already visited, but node 3 is unvisited. Update dist[3] = dist[1] + 1 = 2. Push 3 into the queue.
- queue = [2, 3]
- dist = {0: 0, 1: 1, 2: 1, 3: 2}

4. Target Reached: Since we popped or discovered 3 (or check upon popping), we see that target 3 has a distance of 2. (We could also process node 2, which sees neighbor 3 is already visited with a distance $\le 1+1$).

Result

The shortest path distance from node 0 to node 3 is 2 hops. The valid paths achieving this are 0 -> 1 -> 3 or 0 -> 2 -> 3.

Now it is your turn to apply the layer-by-layer ripple model to a slight mutation of our working example. Recall our initial graph with edges $\{(0,1),(0,2),(1,3),(2,3)\}$, where the shortest path from 0 to 3 takes 2 hops ($0\to 1\to 3$ or $0\to 2\to 3$).

Imagine we add a direct edge $(0,3)$ to the graph, so the edge list becomes $\{(0,1),(0,2),(1,3),(2,3),(0,3)\}$. When BFS pops node 0 from the queue, it iterates through all its unvisited neighbors: 1, 2, and now 3.

Think about what happens to dist[3] and how the queue processes this new direct route. Work through the steps mentally before answering the question below.

We have successfully tracked our unweighted graph from start node 0 to target node 3, discovering that our standard BFS guarantees a minimum path length of 2 through intermediate steps like $0\to 1\to 3$. But what happens when the rules of the graph change? Suppose our edges now carry weights, such that $0\to 1$ costs 10 units while $0\to 2\to 3$ costs a total of 2 units. A pure unweighted BFS still only counts edge hops, meaning it would still falsely treat $0\to 1\to 3$ and $0\to 2\to 3$ as equally valid paths of length 2, ignoring the actual edge weights entirely.

To handle weighted graphs, standard BFS must hand over the baton to Dijkstra's algorithm, substituting a priority queue for our standard FIFO queue. However, if every edge weight becomes uniform again—or if we simply want to find the shortest path from multiple simultaneous starting points instead of just node 0—our core BFS framework scales seamlessly. By pre-populating the queue with all source nodes at distance 0 before the main loop begins, the very same ripple pattern expands outward to find the nearest source for every target.

Recognizing when standard BFS is insufficient prevents catastrophic bugs in routing and pathfinding systems. If you encounter negative edge weights, BFS and Dijkstra both fail, requiring specialized algorithms like Bellman-Ford. But whenever uniform step costs govern the environment, the layer-by-layer guarantees we observed in our 4-node graph remain your most reliable, linear-time tool.