From BFS Labels to a Route
Breadth-first search (BFS) records more than which vertices it discovers. Each discovered vertex has a distance label and a parent pointer. Together, these give a compact record of a route from the source and evidence that no shorter route exists. The evidence is useful when checking an algorithm’s output: a route can be checked edge by edge, while distance labels can be checked against all the directed edges.
Throughout, a directed graph is finite and simple. A directed walk from \(s\) to \(v\) is a sequence \(s=v_0,v_1,\ldots,v_k=v\) such that \(v_{i-1}\to v_i\) is an arc for every \(i\). Its length is the number \(k\) of arcs. A directed path is a directed walk with no repeated vertices. The directed distance from \(s\) to \(v\) is the minimum length of a directed path from \(s\) to \(v\), when one exists; otherwise the distance is \(\infty\). The source has distance \(0\).
To reconstruct a route to a discovered vertex \(v\), repeatedly follow its parent pointer: \(v,p(v),p(p(v)),\ldots\). Read this sequence in reverse to get a route from \(s\) to \(v\). Each parent step decreases the label by one, so the process reaches \(s\) after exactly \(d(v)\) steps. The resulting route follows directed arcs in the forward direction when read from \(s\) to \(v\).
What Makes the Labels a Certificate?
There are two separate checks. First, every finite label must be realized by a parent route of that length. Second, no directed arc out of a reachable vertex may lead to a label more than one larger than its own. The first check supplies a route; the second prevents any route from reaching a vertex in fewer steps than its label suggests.
- \(d(s)=0\) and \(p(s)=\mathrm{NIL}\).
- Every vertex with finite label other than \(s\) has a parent \(u\) with an arc \(u\to v\) and \(d(v)=d(u)+1\).
- For every arc \(u\to v\) whose tail \(u\) has finite label, \(v\) has finite label and \(d(v)\le d(u)+1\).
Proof. First consider a vertex \(v\) with finite label. If \(v\ne s\), following its parent reduces the label by exactly one and follows an arc backwards along the parent relation. Repeating this step cannot continue indefinitely: the labels are nonnegative integers and decrease at each step. It must reach a vertex with label \(0\). The parent condition applies to every finite vertex other than \(s\), so a finite vertex other than \(s\) cannot have label \(0\). Thus the chain reaches \(s\). Reading the chain from \(s\) to \(v\) gives a directed path of length \(d(v)\), so the directed distance to \(v\) is at most \(d(v)\).
Now take any directed path \(s=x_0,x_1,\ldots,x_k=v\). We show, one arc at a time, that \(d(x_i)\le i\). For \(i=0\), \(d(x_0)=d(s)=0\). If \(d(x_i)\le i\), the arc condition on \(x_i\to x_{i+1}\) gives \(d(x_{i+1})\le d(x_i)+1\le i+1\). Hence \(d(v)\le k\). This holds for every directed path from \(s\) to \(v\), so no such path is shorter than \(d(v)\). Together with the parent path of length \(d(v)\), this proves that \(d(v)\) is the directed distance. Finally, if a vertex labelled \(\infty\) were reachable, a path from \(s\) to it would have a first arc from a finite-labelled vertex to an infinite-labelled one. The arc condition forbids that. Therefore every vertex labelled \(\infty\) is unreachable. \(\square\)
For BFS, the parent condition holds because a newly discovered vertex \(v\) is assigned \(d(v)=d(u)+1\) when it is first reached from the vertex \(u\) being processed. The arc condition holds because BFS processes vertices in nondecreasing order of their labels: when it examines \(u\to v\), either \(v\) is newly assigned \(d(u)+1\), or \(v\) already has a label no larger than \(d(u)+1\). Thus the theorem explains why the parent pointers and labels produced by BFS certify shortest distances. As established in the earlier material on BFS layers, the queue processes one distance layer before the next.
Tracing the Pointers, Including an Unreachable Vertex
Worked Example: Reconstructing a BFS Route
Let \(G=(V,E)\) be the directed graph with \(V=\{s,a,b,c,d,e,f,z\}\) and \(E=\{s\to a,s\to b,a\to c,a\to d,b\to c,c\to e,d\to e,e\to f,z\to a\}\). Run BFS from \(s\), examining outgoing arcs in the order written when there is a choice.
Initially the queue is \([s]\), with \(d(s)=0\) and \(p(s)=\mathrm{NIL}\); every other vertex has label \(\infty\) and parent \(\mathrm{NIL}\). The trace is:
| Vertex removed from queue | Newly discovered vertices | Queue afterward |
|---|---|---|
| \(s\) | \(a,b\), each with label \(1\) and parent \(s\) | \([a,b]\) |
| \(a\) | \(c,d\), each with label \(2\) and parent \(a\) | \([b,c,d]\) |
| \(b\) | None; \(c\) already has a label | \([c,d]\) |
| \(c\) | \(e\), with label \(3\) and parent \(c\) | \([d,e]\) |
| \(d\) | None; \(e\) already has a label | \([e]\) |
| \(e\) | \(f\), with label \(4\) and parent \(e\) | \([f]\) |
| \(f\) | None | \([]\) |
The parent chain for \(f\) is \(f,e,c,a,s\). Reversing it gives \(s,a,c,e,f\). Its arcs are \(s\to a\), \(a\to c\), \(c\to e\), and \(e\to f\), so it is a directed path. It has \(4\) arcs, as follows by counting the four consecutive pairs in the sequence, and \(d(f)=4\).
For the certificate check, the labels are \(d(s)=0\), \(d(a)=d(b)=1\), \(d(c)=d(d)=2\), \(d(e)=3\), and \(d(f)=4\). Each non-source finite vertex has the displayed parent arc and a label one greater than its parent. The arc labels also satisfy the required inequalities: the arcs out of \(s\) lead to labels \(1\); those out of \(a\) lead to labels \(2\); \(b\to c\) leads to label \(2\); \(c\to e\) and \(d\to e\) lead to label \(3\); and \(e\to f\) leads to label \(4\). In each case the head label equals the tail label plus \(1\).
The finite-labelled set is \(S=\{s,a,b,c,d,e,f\}\). Every arc with tail in \(S\) also has its head in \(S\); in particular, the arc \(z\to a\) points into \(S\), not out of it. Thus no directed path starting at \(s\) can leave \(S\), and \(z\), whose label remains \(\infty\), is unreachable. As a second check of the route length, the certificate theorem says \(d(f)=4\), and the reconstructed parent path has exactly \(4\) arcs.
Checking a Claimed Route and Its Length
A proposed route can be checked directly without trusting its parent pointers. Check that it starts and ends at the claimed vertices, and that every consecutive pair is a directed arc in the required direction. If it is claimed to be a path, also check that no vertex repeats. Its length is the number of arcs, not the number of vertices. To verify that it is shortest, compare that length with a valid shortest-path certificate, or establish the certificate conditions for the labels and parents.
Worked Example: A Valid Route That Is Not Shortest
Let \(G=(V,E)\) have \(V=\{r,a,b,c,t\}\) and \(E=\{r\to a,r\to b,a\to b,a\to c,b\to t,c\to t\}\). Consider the claimed route \(r,a,b,t\).
Its consecutive pairs use arcs \(r\to a\), \(a\to b\), and \(b\to t\), so it is a directed path. It has \(3\) arcs, not \(4\): the sequence has \(4\) vertices and therefore \(4-1=3\) consecutive pairs.
To test whether it is shortest, run BFS from \(r\). Initially the queue is \([r]\). Processing \(r\) discovers \(a,b\), each at label \(1\), so the queue becomes \([a,b]\). Processing \(a\) discovers \(c\) at label \(2\); \(b\) is already discovered, so the queue becomes \([b,c]\). Processing \(b\) discovers \(t\) at label \(2\), so the queue becomes \([c,t]\). Processing \(c\) finds \(t\) already discovered; processing \(t\) adds no vertex.
The parent of \(t\) is \(b\), and the parent chain gives \(r,b,t\), using the arcs \(r\to b\) and \(b\to t\). Its length is \(2\), since it has two consecutive pairs. The labels and parents satisfy the certificate conditions: \(a,b\) have parent \(r\) and label \(1\); \(c\) has parent \(a\) and label \(2\); and \(t\) has parent \(b\) and label \(2\). For the arc inequalities, \(r\to a\) and \(r\to b\) lead to label \(1\), \(a\to b\) leads to label \(1\le 2\), \(a\to c\) leads to \(2\), \(b\to t\) leads to \(2\), and \(c\to t\) leads to \(2\le 3\). The certificate proves that \(d(t)=2\). Thus the claimed route is valid and its length is \(3\), but it is not a shortest path.
Check: the parent path \(r,b,t\) has \(2\) arcs, and the certificate establishes that no route to \(t\) has fewer than \(2\) arcs. The proposed path has \(3\) arcs, so it is strictly longer.
Auditing a Parent Choice
Parent pointers depend on the order in which BFS examines outgoing arcs. If there are multiple shortest paths, different examination orders can give different parents. This does not make one result less correct: the parent arc and label conditions, not a particular choice among ties, are what certify the distance. Conversely, a parent chain can be a valid route without being shortest, so checking the parent chain alone is not enough.
Worked Example: Detecting a Misleading Parent Chain
Let \(G=(V,E)\) have \(V=\{q,a,b,c,x\}\) and \(E=\{q\to a,q\to b,a\to c,b\to c,c\to x,b\to x\}\). Suppose someone proposes labels \(d(q)=0\), \(d(a)=d(b)=1\), \(d(c)=2\), \(d(x)=3\), with parents \(p(a)=q\), \(p(b)=q\), \(p(c)=a\), and \(p(x)=c\).
Every parent pointer does follow an arc, and each parent label is one less than its child label. Following the pointers gives \(q,a,c,x\), a directed path of length \(3\). But this alone does not prove that the label \(3\) is shortest. Check every arc leaving a finite-labelled vertex. The arcs \(q\to a\) and \(q\to b\) lead to label \(1\), \(a\to c\) leads to label \(2\), \(b\to c\) leads to label \(2\), and \(c\to x\) leads to label \(3\). The remaining arc, \(b\to x\), requires \(d(x)\le d(b)+1=1+1=2\). The proposed label \(d(x)=3\) violates this inequality.
The correction is \(d(x)=2\) with parent \(p(x)=b\). The corrected parent route \(q,b,x\) uses \(q\to b\) and \(b\to x\), so it has \(2\) arcs. The other labels and parent pointers are unchanged. Rechecking the arc inequalities, \(b\to x\) now gives \(2\le 1+1=2\), while \(c\to x\) gives \(2\le 2+1=3\); the other four arcs retain the values checked above. All parent relations and arc inequalities hold, so the certificate theorem confirms that the corrected label \(2\) is the distance to \(x\).
Common Pitfall: A Parent Path Is Not the Whole Proof
In the last example, the sequence \(q,a,c,x\) really is a directed path of length \(3\). The mistake is to infer from that fact that the distance is \(3\). A path of length \(3\) proves only that the distance is at most \(3\); a shorter path may exist. The missed arc \(b\to x\) exposes the shorter route and violates the arc inequality. To certify shortestness, verify both that the parent chain gives a route of the labelled length and that every relevant arc respects the labels.
For unreachable vertices, a parent value of \(\mathrm{NIL}\) by itself is not enough to distinguish an undiscovered vertex from the source. Check the label as well: the source has label \(0\), while an unreachable vertex has label \(\infty\). To justify the claim of unreachability, verify that every arc leaving a finite-labelled vertex ends at another finite-labelled vertex. Any path from the source to an infinite-labelled vertex would have to use a first arc leaving the finite-labelled set, which this check rules out.
Check Your Understanding
Use parent arcs and distance labels to justify each answer.
- If the parent chain from \(s\) to \(v\) has \(5\) arcs, what must the label \(d(v)\) be in a valid BFS certificate?
- Why does a valid directed path of length \(4\) to \(v\) show that the distance to \(v\) is at most \(4\), but not necessarily equal to \(4\)?
- In the graph with vertices \(\{s,a,b,t\}\) and arcs \(s\to a,a\to t,s\to b,b\to t\), give two possible shortest parent paths from \(s\) to \(t\).
- What certificate condition rules out an arc from a finite-labelled vertex to an infinite-labelled vertex?
- Explain why checking only the parent chain can miss a shorter route, using the arc \(b\to x\) in the last worked example.