Building a Distance Table from a Root
A distance table organizes the shortest-path information from one chosen vertex. Rather than compare every possible route separately, we collect vertices in layers: first the root, then its neighbors, then vertices reached in two edges, and so on. This is the basic idea behind breadth-first search. The resulting table gives a systematic way to read off distances and to check that a route is shortest.
Throughout, graphs are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent; its length is its number of edges. If a path joins vertices \(u\) and \(v\), their distance \(d(u,v)\) is the minimum length among all such paths. The minimum exists because the graph is finite and the possible path lengths are nonnegative integers. If there is no path from \(u\) to \(v\), we say there is no finite distance between them.
To construct the layers, start with \(L_0=\{r\}\). At each stage, examine the neighbors of vertices in the current layer. Any neighbor not already listed belongs to the next layer. “Not already listed” matters: a vertex that has a neighbor in the current layer may nevertheless have been discovered earlier, in which case it keeps its earlier layer.
Why the Layers Give the Distances
Proof. We prove the claim successively for \(k=0,1,2,\ldots\). For \(k=0\), the only vertex at distance zero from \(r\) is \(r\), so \(L_0=\{r\}\) is correct. Suppose that \(L_k\) contains exactly the vertices at distance \(k\), and that all earlier layers have been formed correctly. Each vertex \(v\) newly added while examining neighbors of \(L_k\) has a neighbor \(u\in L_k\). A path of length \(k\) from \(r\) to \(u\), followed by the edge \(uv\), gives a route of length \(k+1\) to \(v\). This route might repeat a vertex; if it does, removing the portion between two repeated occurrences gives a shorter route to \(v\), and hence a path no longer than \(k+1\). But \(v\) was not in any earlier layer, so its distance is not at most \(k\). Therefore its distance is exactly \(k+1\).
Conversely, let \(v\) have distance \(k+1\). Take a shortest path from \(r\) to \(v\), and let \(u\) be the vertex immediately before \(v\) on that path. The prefix ending at \(u\) has length \(k\) and is shortest: if a shorter path to \(u\) existed, appending \(uv\) would give a route to \(v\) shorter than \(k+1\), from which any repetitions could be removed. Thus \(u\in L_k\), and when the neighbors of \(L_k\) are examined, \(v\) is added unless it has already been added. It cannot have been added earlier, because that would give it distance at most \(k\). Hence \(v\in L_{k+1}\). Both inclusions hold, completing the induction. \(\square\)
The procedure can be implemented with a queue: place the root in the queue, repeatedly remove the first vertex and add any previously undiscovered neighbors to the back. Record a vertex's distance when it is first added. The order of vertices within a layer can vary; the distances and layers do not.
Worked Example: Building the Table Step by Step
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e,f,g\}\) and \(E=\{ab,ac,bd,ce,de,df,fg\}\). Construct the distance table from root \(a\). In the queue column, the entries are shown from front to back. A vertex is marked as discovered as soon as it is added, so it is not added a second time.
| Action | New vertices and their labels | Queue after the action |
|---|---|---|
| Initialize | \(a:0\) | \([a]\) |
| Remove \(a\) | \(b:1,\ c:1\) | \([b,c]\) |
| Remove \(b\) | \(d:2\) | \([c,d]\) |
| Remove \(c\) | \(e:2\) | \([d,e]\) |
| Remove \(d\) | \(f:3\) | \([e,f]\) |
| Remove \(e\) | None; \(c,d\) are already discovered | \([f]\) |
| Remove \(f\) | \(g:4\) | \([g]\) |
| Remove \(g\) | None; \(f\) is already discovered | \([]\) |
Reading the labels by distance gives \(L_0=\{a\}\), \(L_1=\{b,c\}\), \(L_2=\{d,e\}\), \(L_3=\{f\}\), and \(L_4=\{g\}\). The distance table is therefore \(d(a,a)=0\), \(d(a,b)=d(a,c)=1\), \(d(a,d)=d(a,e)=2\), \(d(a,f)=3\), and \(d(a,g)=4\).
Check: Paths witnessing the nonzero entries are \(a,b\) and \(a,c\) (length \(1\)); \(a,b,d\) and \(a,c,e\) (length \(2\)); \(a,b,d,f\) (length \(3\)); and \(a,b,d,f,g\) (length \(4\)). The successive-layer proposition shows that none of these distances can be smaller than its layer number. The queue is empty at the end, and all seven vertices have been discovered.
Reading and Checking a Distance Table
A layer number is a distance, not a count of vertices or a count of steps in the queue procedure. To check a proposed entry, use two pieces of information: exhibit a path of the claimed length, and establish from the layers that no shorter path exists. Listing one route alone proves only an upper bound on the distance; another route might be shorter.
Worked Example: A Shortcut Changes the Distances
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56,14,46\}\). Find the distance table from vertex \(1\).
The root gives \(L_0=\{1\}\). Its neighbors are \(2\) and \(4\), so \(L_1=\{2,4\}\). The neighbors of \(2\) and \(4\) are respectively \(\{1,3\}\) and \(\{1,3,5,6\}\). Excluding vertices already in \(L_0\) or \(L_1\), the next layer is \(L_2=\{3,5,6\}\). Every vertex has now been reached, so the table is \(d(1,1)=0\), \(d(1,2)=d(1,4)=1\), and \(d(1,3)=d(1,5)=d(1,6)=2\).
Paths that attain the last three distances are \(1,2,3\), \(1,4,5\), and \(1,4,6\), each of length \(2\). The edges \(13\), \(15\), and \(16\) are absent from the stated edge set, so none of \(3,5,6\) has distance \(1\). The layer construction rules out a shorter route. Notice that the edges \(14\) and \(46\) create a short route to \(6\); following the long route \(1,2,3,4,5,6\) would not give its distance.
Check: the displayed paths use the listed edges: \(12,23\) for the route to \(3\); \(14,45\) for the route to \(5\); and \(14,46\) for the route to \(6\). Each route has two edges, while each endpoint is not adjacent to \(1\). Thus each of these three distances is exactly \(2\).
A distance table is relative to its root. Changing the root can change the layers, so a table from one vertex does not by itself give the distances from every other vertex. Also, a root may fail to reach some vertices if the graph is disconnected. In that case the construction still correctly lists the root's reachable vertices, but it does not create a finite-distance entry for the others.
Worked Example: A Root That Cannot Reach Every Vertex
Let \(G=(V,E)\), where \(V=\{p,q,r,s,t\}\) and \(E=\{pq,qr,st\}\), and choose root \(p\). The first layer is \(L_0=\{p\}\). The neighbors of \(p\) give \(L_1=\{q\}\). Examining \(q\) gives the new vertex \(r\), so \(L_2=\{r\}\). Vertex \(r\) has no new neighbors. The table from \(p\) is therefore \(p:0,\ q:1,\ r:2\). Vertices \(s,t\) do not appear: there is no path from \(p\) to either of them.
Check: the paths \(p,q\) and \(p,q,r\) have lengths \(1\) and \(2\), respectively. The edge list contains no edge joining \(\{p,q,r\}\) to \(\{s,t\}\), so a path starting at \(p\) cannot reach \(s\) or \(t\). In particular, the edge \(st\) does not put either endpoint into a layer from \(p\).
Common Pitfalls
Counting vertices instead of edges. In the first example, the route \(a,b,d,e\) contains four vertices but has length \(3\), because it uses three edges. In general, a path with \(j+1\) vertices has length \(j\).
Treating any path length as the distance. For the same graph, the route \(a,b,d,e\) proves that there is a route of length \(3\) to \(e\), but it does not prove \(d(a,e)=3\). The route \(a,c,e\) has length \(2\), and the table puts \(e\) in \(L_2\); hence \(d(a,e)=2\).
Adding a vertex more than once. In the first example, \(d\) is adjacent to both \(b\) and \(e\), and both \(b\) and \(e\) are examined during the procedure. Once \(d\) has been discovered from \(b\), examining \(e\) must not assign \(d\) another label. Its first discovery gives its shortest distance.
Assuming every vertex appears. The table is rooted at one vertex, so it covers only vertices reachable from that root. In the third example, the edge \(st\) does not make \(s\) or \(t\) reachable from \(p\).
Distance tables are useful whenever a problem asks for shortest routes from a specified starting point. The layer order prevents missed shorter routes, while the recorded paths make each finite entry easy to verify. The key practice is to mark vertices when first discovered and to keep each layer separate from the next.
Check Your Understanding
For each question, use the layer construction and distinguish a route of a given length from proof that the route is shortest.
- For \(V=\{u,v,w,x\}\), \(E=\{uv,uw,vx,wx\}\), and root \(u\), list all layers and give the distance table.
- In a distance table from root \(r\), why should a vertex discovered while examining \(L_k\) be assigned to \(L_{k+1}\), provided it has not appeared earlier?
- For \(V=\{1,2,3,4,5\}\), \(E=\{12,23,34,45,14\}\), construct the distance table from \(1\). Give a shortest path to each vertex.
- Explain why displaying a path of length \(4\) from \(r\) to \(v\) does not, by itself, prove that \(d(r,v)=4\).
- For \(V=\{a,b,c,d\}\), \(E=\{ab,cd\}\), and root \(a\), which vertices appear in the distance table? Explain why the other vertices do not.