One Search from Several Sources
Suppose a network has several service stations, and each location should be assigned to a closest station by number of edges. Running a separate search from every station repeats work. Instead, breadth-first search (BFS) can begin with all stations in the queue at once. The resulting distance label of a vertex is its distance from the nearest source. If several sources are equally near, the distance is still unambiguous, but the nearest source need not be.
Throughout, graphs are finite, simple and undirected. A path has length equal to its number of edges. A source set \(S\) is assumed to be nonempty. Vertices may lie in components containing no source; their distance from every source is treated as infinite, and they remain undiscovered.
The standard multi-source BFS computes the distances by assigning label \(0\) to every source, putting every source in one queue, and then applying the usual BFS rule: remove the front vertex and give each as-yet-undiscovered neighbor a label one greater than its own. In this tutorial, a vertex with no finite label is written \(\infty\). The sources are all initialized before any vertex is removed from the queue; this is essential.
Set \(d_S(s)=0\) for each \(s\in S\), mark those vertices discovered, and enqueue all of them.
Remove the front vertex \(u\). For every undiscovered neighbor \(v\), set \(d_S(v)=d_S(u)+1\), record \(u\) as a parent if a path certificate is wanted, and enqueue \(v\).
Stop when the queue is empty. Any vertex still undiscovered has label \(\infty\). The order in which tied sources were enqueued can choose one nearest source, but does not change the distance labels.
Why the Distance Labels Are Correct
We use the FIFO property of the queue. At every stage, queued vertices have labels in nondecreasing order. Indeed, initially all queued sources have label \(0\). If the front vertex has label \(r\), every newly discovered neighbor is appended with label \(r+1\); the vertices already in the queue have labels at least \(r\), and the labels appended are all \(r+1\). Thus the order remains nondecreasing. In particular, vertices are removed from the queue in nondecreasing label order.
Proof. First, each finite label is the length of a path from some source. This holds for a source, whose label is \(0\). Whenever a new neighbor receives label \(r+1\) from a vertex with label \(r\), append their edge to the path certifying the label \(r\). Consequently, for every reached vertex \(v\), some source has a path of length equal to its label, so \(d_S(v)\) is at most that label.
For the reverse inequality, take any vertex \(v\) connected to a source, and let \(k=d_S(v)\). Choose a shortest path \(s=v_0,v_1,\ldots,v_k=v\) from a source \(s\in S\) to \(v\). We show successively that \(v_i\) receives a label at most \(i\). The claim holds for \(v_0=s\), whose label is \(0\). Suppose it holds for \(v_{i-1}\). If \(v_i\) has already been discovered when \(v_{i-1}\) is removed, it was discovered while processing an earlier-removed vertex \(w\). By the FIFO property, \(w\)'s label is at most the label of \(v_{i-1}\), hence at most \(i-1\). Processing \(w\) assigned \(v_i\) the label \(d_S(w)+1\), which is at most \(i\). If \(v_i\) has not already been discovered, processing \(v_{i-1}\) assigns it the label \(d_S(v_{i-1})+1\), again at most \(i\). This proves the claim, including the case of an earlier discovery by another route. In particular, \(v\) is reached with a label at most \(k\). The first part of the proof says its label is at least \(d_S(v)=k\); therefore its label equals \(k\). Finally, a vertex is reached only by following a path from an initialized source. Thus a vertex is reached exactly when it is connected to some source, which is exactly when its distance to the nearest source is finite. \(\square\)
The theorem determines distances, but a single parent or source label need not display every tie. A convenient way to compute the full nearest-source sets is to use the distance labels after BFS is complete.
Proof. Let \(v\notin S\) have finite label \(k\). If \(s\in A(v)\), a shortest path from \(s\) to \(v\) has length \(k\). Its penultimate vertex \(u\) is adjacent to \(v\), and the part of that path from \(s\) to \(u\) has length \(k-1\). Hence \(d_S(u)\le k-1\). If it were less than \(k-1\), appending the edge \(uv\) would give a path from a source to \(v\) shorter than \(k\); therefore \(d_S(u)=k-1\). Also \(d(s,u)=k-1\), so \(s\in A(u)\). This proves that every member of \(A(v)\) belongs to the displayed union.
Conversely, suppose \(u\) is a neighbor of \(v\) with \(d_S(u)=k-1\), and \(s\in A(u)\). Then \(d(s,u)=k-1\); appending \(uv\) gives a path from \(s\) to \(v\) of length \(k\). Since \(d_S(v)=k\), this path is shortest, so \(s\in A(v)\). This proves the other inclusion. At a source \(s\), the distance is \(0\), and no other source can be at distance \(0\) from it in a simple graph, so its nearest-source set is exactly \(\{s\}\). \(\square\)
Worked Traces and Ties
Worked Example: Distances, Ties, and an Unreached Component
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e,f,x,g,h\}\) and \(E=\{ab,ac,bd,cd,ce,de,df,ef,bx,fx,gh\}\). Take the source set \(S=\{a,e\}\). For the queue trace, enqueue \(a\) before \(e\), and inspect each vertex’s neighbors in alphabetical order.
Initially, \(d_S(a)=d_S(e)=0\) and the queue is \([a,e]\). The table records the queue after each removal and the vertices newly discovered at that step.
| Removed | Newly discovered (label) | Queue afterward |
|---|---|---|
| \(a\) (0) | \(b,c\) (1) | \([e,b,c]\) |
| \(e\) (0) | \(d,f\) (1); \(c\) is already discovered | \([b,c,d,f]\) |
| \(b\) (1) | \(x\) (2) | \([c,d,f,x]\) |
| \(c\) (1) | None | \([d,f,x]\) |
| \(d\) (1) | None | \([f,x]\) |
| \(f\) (1) | None; \(x\) is already discovered | \([x]\) |
| \(x\) (2) | None | \([]\) |
The resulting labels are \(d_S(a)=d_S(e)=0\), \(d_S(b)=d_S(c)=d_S(d)=d_S(f)=1\), and \(d_S(x)=2\). The component with vertices \(g,h\) has no source, so both labels are \(\infty\). For example, \(g\) and \(h\) are adjacent to each other, but neither is connected to \(a\) or \(e\).
To find all ties, apply the nearest-source rule in increasing order of the labels. The sources have \(A(a)=\{a\}\) and \(A(e)=\{e\}\). Vertex \(b\) has a distance-0 neighbor \(a\), so \(A(b)=\{a\}\). Vertex \(c\) has distance-0 neighbors \(a\) and \(e\), so \(A(c)=\{a,e\}\). Vertices \(d\) and \(f\) each have \(e\) as their only distance-0 neighbor, so \(A(d)=A(f)=\{e\}\). Finally, \(x\) has distance-1 neighbors \(b\) and \(f\), giving \(A(x)=A(b)\cup A(f)=\{a,e\}\).
Check: The path \(a,b,x\) has length \(2\), and \(e,f,x\) has length \(2\), so both sources are nearest to \(x\). Vertex \(c\) is adjacent to both sources, so both are nearest to \(c\) at distance \(1\). The labels for \(g,h\) are correctly infinite: their only component is the edge \(gh\), which contains no source.
Worked Example: A Queue Order Chooses One of Two Tied Sources
Let \(G=(V,E)\), where \(V=\{p,q,r,z\}\), \(E=\{pr,qr,rz\}\), and \(S=\{p,q\}\). Enqueue \(p\) before \(q\). Initially the queue is \([p,q]\), and both sources have label \(0\). Removing \(p\) discovers \(r\) with label \(1\), leaving \([q,r]\). Removing \(q\) finds that \(r\) is already discovered, leaving \([r]\). Removing \(r\) discovers \(z\) with label \(2\), leaving \([z]\). Removing \(z\) leaves the empty queue.
The labels are \(d_S(p)=d_S(q)=0\), \(d_S(r)=1\), and \(d_S(z)=2\). This single-parent trace assigns \(r\) to \(p\), and then assigns \(z\) to \(p\) along the parent chain. But both \(p\) and \(q\) are nearest to \(r\), since each is joined to \(r\) by one edge. Both are also nearest to \(z\), by the paths \(p,r,z\) and \(q,r,z\), each of length \(2\).
Check: The nearest-source rule gives \(A(r)=A(p)\cup A(q)=\{p,q\}\), using both neighbors at distance \(0\). It then gives \(A(z)=A(r)=\{p,q\}\), since \(r\) is the only neighbor of \(z\) and has label \(1=2-1\). Thus the chosen parent records one valid nearest source, not necessarily all of them.
Worked Example: A Component with No Source
Let \(G=(V,E)\), where \(V=\{u,v,w,x,y\}\), \(E=\{uv,vw,xy\}\), and \(S=\{u,w\}\). Initialize the queue as \([u,w]\), with both source labels equal to \(0\). Removing \(u\) discovers \(v\) with label \(1\), so the queue becomes \([w,v]\). Removing \(w\) finds \(v\) already discovered, so the queue becomes \([v]\). Removing \(v\) adds no vertex, and the queue becomes empty. The labels are \(0\) at \(u,w\), \(1\) at \(v\), and \(\infty\) at \(x,y\).
The nearest-source set at \(v\) is \(\{u,w\}\): the paths \(u,v\) and \(w,v\) both have length \(1\). The edge \(xy\) forms a separate component with no source, so neither \(x\) nor \(y\) has a finite distance to \(S\).
Check: The computed finite labels match the paths of lengths \(0\) and \(1\) in the component containing the sources. No path from either source can reach \(x\) or \(y\), because the only edge incident with either vertex is \(xy\).
Implementation, Cost, and a Common Mistake
With adjacency lists, the distance search takes \(O(|V|+|E|)\) time: each vertex is enqueued and removed at most once, and each adjacency list is scanned once when its vertex is removed. Initializing the queue takes \(O(|S|)\), which is at most \(O(|V|)\). This bound is for distances and one parent or chosen source per vertex. If the full set \(A(v)\) is explicitly stored for every vertex, the output itself can be large: many vertices may be tied to many sources. The layer rule gives the correct sets, but the cost of building and storing them depends on the number of source labels propagated.
Common mistake: starting a complete BFS from each source in turn. On the graph with \(V=\{a,b,c\}\), \(E=\{ab,bc\}\), and \(S=\{a,c\}\), the correct initial queue is \([a,c]\), with both labels \(0\). If instead a search from \(a\) is completed first, it gives \(c\) label \(2\) along \(a,b,c\). Treating that label as final misses that \(c\) is itself a source, whose distance to the nearest source is \(0\). The correction is to initialize every source at distance \(0\) and enqueue all of them before beginning the search.
Multi-source BFS is useful whenever a query asks for distance to the closest member of a specified set: nearest facility, nearest exit, or the first layer reached by any of several starting points. The distances do not depend on source order. Source order can affect which parent or single nearest-source representative is recorded when there is a tie, so a query requiring every nearest source must retain ties rather than reporting only the first one discovered.
Check Your Understanding
Use the multi-source initialization and the nearest-source rule to answer these questions.
- For \(V=\{a,b,c,d\}\), \(E=\{ab,bc,cd\}\), and \(S=\{a,d\}\), find the distance label of every vertex and the full nearest-source set of \(b\) and \(c\).
- Explain why initializing all sources before the first removal is necessary for the labels to represent distance to the nearest source.
- In a multi-source BFS, what does a parent pointer identify when there are ties? What extra calculation gives all tied nearest sources?
- Suppose a vertex is not reached by the algorithm. What does that imply about its component and its distance to the source set?
- State the FIFO fact used in the distance proof, and explain why it controls the label of a vertex discovered earlier by another route.