Why does BFS find shortest paths? — The ripple analogy

BFS finds shortest paths in unweighted graphs, but why should breadth-first exploration guarantee optimality? Using the analogy of ripples on a pond, we build intuition for the correctness of BFS, see why DFS fails, and understand Dijkstra as a generalization to variable-speed ripples.

Folio Official

March 1, 2026

Every algorithms textbook states matter-of-factly that BFS (breadth-first search) finds shortest paths in unweighted graphs. But why does exploring breadth-first yield shortest paths? Why does DFS fail where BFS succeeds? In this article, we use the analogy of ripples on water to reach the heart of the matter.

1 The ripple analogy

Drop a stone into a still pond. Circular ripples spread outward, expanding at the same speed in every direction. Because the speed is uniform, the first ripple to reach any given point has necessarily traveled the shortest distance.

BFS does exactly the same thing.

Starting from the source $s$ and "sending out ripples," layers form naturally:

Distance 0: ${s}$ (the source itself)
Distance 1: ${A, B}$ (neighbors of $s$ )
Distance 2: ${C, D, E}$ (unvisited neighbors of distance-1 vertices)
Distance 3: ${F}$ (unvisited neighbors of distance-2 vertices)

The queue structure of BFS reproduces this layer-by-layer expansion precisely. All vertices at distance $k$ are processed before any vertex at distance $k + 1$ .

2 Correctness of BFS – why the ripple never lies

Let us state the core guarantee.

Theorem 1 (Shortest-path property of BFS).

In an unweighted graph

G = (V, E)

, when BFS is run from a source vertex

s

, the distance label

d [v]

assigned to each vertex

v

upon its first discovery equals the true shortest-path distance

δ (s, v)

The intuitive reason is as follows.

Remark 2 (The ripple principle).

In BFS, every vertex at distance

k

is discovered exclusively from vertices at distance

k - 1

. The first time a vertex

v

is discovered, it is reached via the last edge of a shortest path to

v

, because:

If $v$ could be reached in fewer than $k$ steps, it would already have been discovered before the layer- $k$ processing began.
Because BFS uses a FIFO queue, vertices with smaller distances are always processed first.

The crucial point is that in an unweighted graph, every edge has the same cost (namely 1). The ripple travels at uniform speed, so the first arrival is guaranteed to be the shortest route.

3 A counterexample: DFS does not find shortest paths

DFS (depth-first search) plunges as deep as possible before backtracking. Its behavior is nothing like a ripple.

Example 3 (DFS fails to find the shortest path).

Consider the following graph, and suppose we want the shortest path from

s

t

The shortest path is

s \to t

(distance 1). But if DFS happens to visit

A

first from

s

, it follows

s \to A \to B \to t

(distance 3). Since

t

is now marked as visited, the direct edge

{s, t}

is never used, and the shortest path is missed entirely.

The fundamental issue with DFS is that by prioritizing depth, it may skip nearby vertices in favor of distant ones. It behaves not like a ripple but like a person navigating a maze by keeping one hand on the wall.

4 Weighted graphs – Dijkstra as a variable-speed ripple

When edges carry weights (distances, costs), the simple ripple of BFS no longer suffices. Different edges have different costs, so the assumption "one step = one unit of distance" breaks down.

Example 4 (BFS fails on weighted graphs).

Let the weight of

s \to A

be 1,

s \to B

be 10,

A \to t

be 100, and

B \to t

be 1. BFS, which counts hops rather than total cost, would select

s \to A \to t

(cost 101), but the true shortest path is

s \to B \to t

(cost 11).

This is where Dijkstra's algorithm enters the picture.

Remark 5 (Dijkstra = a ripple with variable speed).

Dijkstra's algorithm modifies BFS by replacing the ordinary queue with a priority queue (min-heap), so that the vertex with the smallest tentative distance is always processed next. In the ripple analogy, lighter edges allow the wave to propagate faster. Because the fastest wavefront still arrives first, Dijkstra correctly identifies shortest paths.

Theorem 6 (Correctness of Dijkstra (intuition)).

When all edge weights are non-negative, Dijkstra's algorithm correctly computes shortest paths. This relies on the greedy-choice property: "among all unsettled vertices, the one with the smallest tentative distance can be permanently settled."

The ripple analogy also explains why non-negative weights are essential. If a negative-weight edge existed, it would be possible to reach a location more cheaply after the wavefront has already passed through it – a ripple flowing backward. The arrival order would no longer correspond to the cost order, and the greedy choice would break down.

5 The meaning of $O (V + E)$

The time complexity of BFS is $O (∣ V ∣ + ∣ E ∣)$ , meaning that each vertex is visited once and each edge is inspected once.

Remark 7.

This is essentially the cost of reading the entire graph once. Since finding shortest paths clearly requires examining the whole graph, the complexity of BFS is optimal for unweighted shortest paths.

Dijkstra's algorithm, with a binary heap, runs in $O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)$ . The $lo g ∣ V ∣$ overhead compared to BFS is the price of the heap operations – the computational cost of allowing the ripple to travel at different speeds along different edges.

6 Summary

BFS is a uniform-speed ripple. Because every edge has the same cost, the first arrival at any vertex is the shortest path.
DFS is a wall-following walk through a maze; it makes no shortest-path guarantee.
Dijkstra is a variable-speed ripple, correctly computing shortest paths when all weights are non-negative.
When negative edges are present, the ripple analogy breaks down, and a fundamentally different approach – such as Bellman–Ford – is required.

In the next article, we examine the most elegant structure within graph theory: the tree.

Graph Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 フォロワー·105 記事

Why does BFS find shortest paths? — The ripple analogy

1 The ripple analogy

2 Correctness of BFS – why the ripple never lies

3 A counterexample: DFS does not find shortest paths

4 Weighted graphs – Dijkstra as a variable-speed ripple

5 The meaning of $O (V + E)$

6 Summary

あなたの専門知識を世界に発信しよう

Folio Officialの他の記事

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

1 The ripple analogy

2 Correctness of BFS – why the ripple never lies

3 A counterexample: DFS does not find shortest paths

4 Weighted graphs – Dijkstra as a variable-speed ripple

5 The meaning ofO(V+E)

6 Summary

あなたの専門知識を世界に発信しよう

Folio Officialの他の記事

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

5 The meaning of $O (V + E)$