How BFS Creates Shortest Paths

One of the most important properties of Breadth-First Search (BFS) is that it finds a shortest path from a source vertex to every reachable vertex in an unweighted graph.

Here, shortest means the path containing the minimum number of edges.

1. BFS explores level by level

Suppose the source is s:

Distance 0:          s

Distance 1:       A     B

Distance 2:     C   D     E

Distance 3:       F     G

BFS first discovers all vertices at distance 1, then all vertices at distance 2, then distance 3, and so on.

Therefore, when BFS first discovers a vertex v, it has reached v using the minimum possible number of edges.

---

2. The d attribute stores the distance

BFS maintains:

v.d

which represents the distance from the source s to vertex v.

Initially:

s.d = 0

When BFS discovers a new vertex v from vertex u, it performs:

v.d = u.d + 1

Therefore, if:

u.d = 2

then the newly discovered vertex has:

v.d = 3

This corresponds to the path:

s → ... → u → v

which contains one more edge than the path to u.

---

3. The Parent Attribute Creates the Path

BFS also maintains:

v.π

which is the parent (predecessor) of v in the BFS tree.

When v is first discovered from u:

v.π = u

For example:

        s
       / \
      A   B
     / \   \
    C   D   E

The parent relationships are:

A.π = s
B.π = s
C.π = A
D.π = A
E.π = B

Therefore, the path to D can be reconstructed by following parent pointers backward:

D → A → s

and reversing it:

s → A → D

---

4. Why Is This Path Guaranteed to Be Shortest?

The key reason is BFS discovers vertices in increasing order of distance.

For example, BFS does not discover a vertex at distance 3 before processing the vertices at distance 1 and 2 that can reach it.

Thus, when:

v.π = u

BFS has established:

v.d = u.d + 1

If u itself was reached by a shortest path, then:

s → ... → u → v

is also a shortest path to v.

Therefore:

v.d=δ(s,v)​

where δ(s,v) denotes the shortest-path distance from s to v.

---

5. Example

Consider:

        A
       / \
      B   C
       \ / \
        D   E

Let A be the source.

BFS proceeds as:

A
↓
B, C
↓
D, E

The distances are:

A → 0
B → 1
C → 1
D → 2
E → 2

Suppose BFS discovers D from B.

Then:

D.d = B.d + 1
    = 1 + 1
    = 2

D.π = B

Therefore, the BFS tree gives:

A → B → D

which contains 2 edges.

If another path from A to D existed with only 1 edge, BFS would have discovered D when processing A. Since that did not happen, the 2-edge path is shortest.

---

6. Important CLRS Result

The central correctness result from :

v.d=δ(s,v)​

for every vertex v reachable from s.

Furthermore, when:

$$v.\pi =u$$

BFS ensures:

$$v.d=u.d+1$$

Therefore, a shortest path to v can be obtained by taking a shortest path to its parent v.π, followed by the edge:

(v.π,v)

Summary

BFS creates shortest paths because it explores the graph level by level. When a vertex is first discovered, it is reached using the minimum possible number of edges. The d attribute records this minimum distance, while the π (parent) attribute records how to reconstruct the corresponding shortest path.

Note: This shortest-path property applies to unweighted graphs, or graphs in which every edge has the same weight. For weighted graphs, algorithms such as Dijkstra's algorithm are generally used.