A girl and a robot thinking together

Let’s think it through · Start with a story

Every move costs the same one step. The robot searches outward like ripples in water. What does it mean when the first ripple reaches the exit?

Break down the process

Follow the numbered steps, then explain them in your own words
  1. StartDistance 0
  2. Adjacent cellsDistance 1
  3. Next cellsDistance 2
  4. First exit reachedFewest steps

In an unweighted graph, or one where every edge has equal cost, BFS can find a path with the fewest edges.

It explores all points reachable in fewer steps first, so it will not miss a shorter route. To reconstruct the path, you also need to record where each point came from.

See how the queue determines the exploration order

The graph has edges A—B, A—C, B—D, and C—E. Neighbors are enqueued in alphabetical order; the front of the queue is on the left.

Step 1 · Start at A
A

A is discovered, at distance 0.

Step 2 · Dequeue A
BC

Enqueue and mark the undiscovered neighbors B and C. They are both at distance 1.

Step 3 · Dequeue B
CD

Enqueue D at distance 2. C is still ahead of D.

Step 4 · Dequeue C
DE

Enqueue E at distance 2. The first layer has now been processed.

Step 5 · Dequeue D and E
Empty queue

There are no undiscovered neighbors. This example visits A, B, C, D, E in that order.

01Why can BFS find a path with the fewest steps?

BFS explores in this order:

0 steps→1 step→2 steps→3 steps...

So when a node is discovered for the first time, there cannot be a shorter path to it that has not been handled yet.

02How do we record distances?

std::vector<int> dist(n, -1);
std::queue<int> q;

dist[start] = 0;
q.push(start);

while (!q.empty()) {
    int u = q.front();
    q.pop();

    for (int v : graph[u]) {
        if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

03Why is dist = -1 useful?

It also means “this node has not been visited yet.”

The first time you set dist[v], you have found the fewest number of edges from the start to v.

04How can we reconstruct a shortest path?

You can also record each node’s predecessor the first time it is discovered:

parent[v] = u;

After reaching the destination, follow parent backward from the destination to the start, then reverse the order.

05When is ordinary BFS not suitable?

When edges have different costs:

Every edge counts as one step

BFS can find a path with the fewest edges.

Edges have different weights

Ordinary BFS does not guarantee the lowest total cost.

06What should we use for a weighted graph?

For nonnegative edge weights, a common algorithm is Dijkstra’s. Other methods may apply when the weights have different special properties.

What you have learned

  • BFS explores in order of increasing number of steps.
  • In an unweighted graph, the distance when a node is first reached is the fewest number of steps.
  • dist can record distance and also serve as a visited marker.
  • parent can be used to reconstruct a shortest path.
  • Ordinary BFS cannot directly solve shortest-path problems with different edge weights.

Next: What Is the Difference Between DFS and BFS?

Your turn

One route has two segments of 10 minutes each; another has three segments of 1 minute each. Is the route with fewer segments the fastest?

Have an answer? Click to see the explanation

No. The two-segment route takes 20 minutes, while the three-segment route takes only 3. In this case, you cannot treat the number of BFS layers as travel time.