Prerequisite: graph representations, DFS and BFS.
A breadth-first search (BFS) normally records one parent per vertex. That is enough to reconstruct one shortest path, but it throws away alternative shortest routes. To count them, we keep a distance and a count, and we treat another edge into an already discovered vertex differently depending on its layer.
This unit extends BFS to count shortest paths in graphs whose edges all have unit length.
1. State the counting problem
Let be a finite directed graph with distinct vertices, no parallel edges, and unit-length edges. The same algorithm works for an undirected graph when its adjacency lists contain each edge in both directions. We count paths by their vertex sequences. Because every edge has length one, a shortest walk cannot repeat a vertex: deleting a nonempty cycle would shorten it. Thus counting shortest walks and counting shortest simple paths give the same answer here.
Definition
(Distance and shortest-path count)
For source , define dist[v] as the least number of edges from to , with infinity for an unreachable vertex. Define ways[v] as the number of paths attaining that distance. There is exactly one zero-edge path from to itself, so dist[s] = 0 and ways[s] = 1; unreachable vertices have count zero.
We assume exact nonnegative-integer arithmetic, a FIFO queue, and adjacency-list access. If the graph permits parallel edges and paths are instead distinguished by edge choices, scan each occurrence and count each separately. If paths mean vertex sequences, duplicate neighbors must first be removed; silently changing conventions changes the answer.
2. One queue, two cases
for each v: dist[v] = infinity; ways[v] = 0
dist[s] = 0; ways[s] = 1
queue = [s]
while queue is not empty:
u = pop_front(queue)
for each neighbor v of u:
if dist[v] == infinity:
dist[v] = dist[u] + 1
ways[v] = ways[u]
push_back(queue, v)
else if dist[v] == dist[u] + 1:
ways[v] = ways[v] + ways[u]
return dist, ways
On first discovery, every shortest route to u can be extended with u -> v; it supplies the first contribution to v. If v was already discovered at exactly dist[u]+1, the new contribution comes from a different last predecessor and must be added. If dist[v] is smaller, this particular extension is too long and contributes nothing. The equality test prevents a longer route from inflating the count.
Only the first discovery enqueues v. This is safe because FIFO BFS processes vertices in nondecreasing distance: before any layer vertex is removed, every layer vertex has been removed. Therefore, when u is removed, every predecessor that can end a shortest path to u has already supplied its contribution. The count used for outgoing edges is complete. Marking only at dequeue or enqueueing v on every equal-distance contribution would need a different accounting argument.
3. Why the count is exact
Theorem
(Correctness and cost of counting BFS)
Let and be as in the problem statement section. When the algorithm halts, for every vertex , dist[v] is the least number of edges from to (infinity if there is none) and ways[v] is the number of shortest paths from to (zero if there is none). With constant-time exact arithmetic, the running time is and the auxiliary space is .
The correctness part is proved below; the cost bound is derived in the section on cost.
Proof
(Induction on the distance layer)
Induct on distance . The source is correct at layer zero. Assume counts are correct when all vertices at distance are removed. Each shortest path to a vertex at distance has a unique penultimate vertex in layer . Removing the final edge gives a shortest path to : otherwise replacing that prefix by a shorter path would give a shorter walk to ; deleting any cycles from that walk would give a still shorter simple path. Conversely, every shortest path to such a neighbor , followed by , is a shortest path to .
Different predecessors give disjoint path sets because their penultimate vertices differ; the graph has no parallel edges. The update sums precisely those sets, once per incoming edge from layer . FIFO ordering ensures that sum is complete before is removed. Induction proves the claim for every reachable vertex. The usual BFS first-discovery argument supplies the distances.
Proof X-ray
Why the queue finalizes the count
Only edges from distance to distance can finish a shortest path to layer . These edges form a directed acyclic layer graph even when the original graph has cycles. FIFO removes every vertex in layer before removing any vertex in layer , so all valid predecessor contributions arrive before a count is used to extend paths.
4. Worked example
Worked example
(Two routes meet at a vertex)
Use edges , , , , , , . Process neighbors in the order listed. Removing discovers with distance 1 and one route each. Removing discovers at distance 2 with one route each. Removing finds already at distance 2 and adds one: ways[c] = 2. Removing discovers with ways[t] = 2; removing adds one more.
| Vertex | ||||||
|---|---|---|---|---|---|---|
| Distance | 0 | 1 | 1 | 2 | 2 | 3 |
| Count | 1 | 1 | 1 | 2 | 1 | 3 |
The three routes to are , , and . Changing the neighbor ordering can change which route is discovered first, but not the final distances or counts.
Concept lensAlgebraic
Path counts as matrix powers
Let be the adjacency matrix, with when is an edge. The entry counts the walks with exactly edges from to . Put : no walk is shorter, and a walk with exactly edges is a shortest path, so , where is the least exponent for which this entry is nonzero. In the graph above, row of has entry at and at , and . The queue computes these entries layer by layer, without forming any matrix power.
Worked example
(Later edges that must be ignored, and an unreachable vertex)
Use edges , , , , , , and an isolated vertex . Removing discovers and at distance 1, each with one route. Removing examines : it is already at distance 1, but , so the edge is ignored and ways[b] stays 1. It then discovers at distance 2 with ways[c] = 1. Removing examines , which is at distance , so ways[c] becomes 2; it examines , which has distance 0 and not 2, so the edge closing a cycle is ignored. Removing ends the search. The vertex is never discovered, so dist[z] stays infinity and ways[z] stays 0. The two shortest routes to are and ; the walk has three edges and is not counted.
Worked example
(Counts multiply through a bottleneck)
Use edges , , , , , , , . The layers are , , , , at distances 0 to 4. Removing discovers with ways[m] = 1, and removing adds one more, so ways[m] = 2. Removing discovers and , each inheriting ways = 2. Removing discovers with ways[t] = 2, and removing adds 2, so ways[t] = 4. The result is : every route passes through , so the two independent choices before and the two after it multiply. The same pattern with such diamonds in a chain gives routes from to the end, which shows how fast the counts can grow.
Common mistake
(Skipping every vertex that was already discovered)
Ordinary BFS ignores an edge into an already discovered vertex, since the vertex already has a parent. If that rule is copied into the counting algorithm, the second route in the first worked example is lost: ways[c] would stay 1 instead of 2, because would be skipped. For counting, an edge into a discovered vertex must still be examined, and it contributes exactly when dist[v] == dist[u] + 1.
Common mistake
(Adding the count on every edge into v)
The opposite error is to write ways[v] = ways[v] + ways[u] for every edge with discovered, without the equality test. With edges , , , the vertex has distance 1 and exactly one shortest path. Removing examines , and without the test ways[b] would become 2, counting the walk of length 2, which is not a shortest path.
5. Cost and limitations
Each vertex is enqueued and removed at most once, and each adjacency entry of a reachable vertex is scanned once. Initializing all arrays costs , so under a unit-cost exact-arithmetic model the time is and auxiliary space is , excluding the adjacency lists. Counts can grow exponentially in the number of vertices. Real fixed-width integers can overflow; arbitrary-precision addition costs depend on the number of bits, so the unit-cost bound does not describe bit complexity. If counts are computed modulo , the output is only a residue: a zero residue does not prove there are no shortest paths.
This proof relies on every edge having unit length. For unequal weights, ordinary BFS layers need not be shortest-distance layers; one must use a suitable weighted shortest-path method and establish when counts are final. In particular, zero-weight edges or cycles introduce additional complications and are outside this chapter's counting contract.
Counterexample mode
Counting by BFS layers is wrong for weighted edges
Claim: the same algorithm counts shortest paths when edges have positive weights, with dist read as weighted distance. Take edges , , , of weight 1 and of weight 3. The weighted shortest distance from to is 2, attained by exactly two paths, and ; the direct edge costs 3. The algorithm counts edges, not weights: removing discovers , and , all at distance 1, with ways[t] = 1, and the later edges and are ignored because . It reports distance 1 and one path, the direct edge, which is not a shortest weighted path at all. The unit-length hypothesis is exactly what makes the number of edges equal the distance, so the theorem cannot be applied here; a weighted shortest-path method is required.
6. Quick checks
Quick check
(In the first worked example, what are dist[t] and ways[t] if the edge is deleted?)
Solution · Answer
Deleting leaves the routes and . The distance of is still 3, and ways[t] = ways[c] = 2.
Quick check
(Why is ways[u] not added to ways[v] when the edge joins two vertices with dist[u] == dist[v]?)
Solution · Answer
A shortest path to followed by has dist[u] + 1 edges, which is one more than dist[v]. It is a walk to but not a shortest path, so it must not be counted.
Quick check
(For edges , , , , , , , , find dist[t] and ways[t].)
Solution · Answer
The layers are , , , , so dist[t] = 3. Each of and is reached from both and , so ways[c] = ways[d] = 2, and ways[t] = 2 + 2 = 4. Equivalently, a shortest path chooses one of and one of : paths.
Quick check
(The algorithm is run with all counts reduced modulo 1000, and ways[t] is reported as 0. Can we conclude that is unreachable?)
Solution · Answer
No. A count of exactly 1000 (or 2000, and so on) also reduces to 0. Reachability is decided by whether dist[t] is finite, not by the residue.