When every edge costs one, BFS explores vertices in increasing number of edges. If edges can cost zero or one, the shortest path means the smallest sum of weights, not the fewest edges. A zero-cost detour may beat a direct cost-one edge. Dijkstra's algorithm handles the weights, but the special two-value structure allows a simpler queue: put a zero-cost improvement at the front and a cost-one improvement at the back.
Setup and revision roadmap
Definition 16.2.1
(Zero-one shortest distance)
Let be a finite directed graph with source and edge weights . Parallel edges and self-loops are allowed: each edge is a separate adjacency-list entry. For an undirected graph, put both directed incidences in the lists, retaining the same weight. A path costs the sum of its edge weights, and denotes the minimum cost from to , or if unreachable. A zero-edge path gives . Nonnegative cycles can be deleted without increasing cost, so each reachable minimum is attained by a simple path.
First trace the deque and watch a tentative label improve. Then prove the two-consecutive-keys invariant and use it to justify settling a vertex. Finally count edge scans and queue entries. Treat a stored queue key as a snapshot: it is not silently updated when the vertex's current distance improves.
Algorithm with explicit stale entries
Use a deque of pairs (key, vertex) and a Boolean settled array. Assume constant-time operations at both ends and exact integer addition/comparison.
for each v: dist[v] = infinity; settled[v] = false
dist[s] = 0
D = [(0,s)] # front is left
while D is not empty:
(k,u) = pop_front(D)
if settled[u] or k != dist[u]: continue
settled[u] = true
for each edge (u,v,w) in adjacency order:
if not settled[v] and k + w < dist[v]:
dist[v] = k + w
if w == 0: push_front(D, (dist[v],v))
else: push_back(D, (dist[v],v))
return dist
Every finite label is the cost of an actual discovered walk. A strict improvement creates a new snapshot; the older one remains in the deque and is discarded when popped. Equal candidates do not create entries. A vertex is settled only when a current snapshot is removed, not when it is first discovered.
Concept lensCombinatorial
Distance levels closed under zero-weight edges
Let . Then is the set reachable from by zero-weight edges, and is the set of vertices outside earlier levels reachable by zero-weight edges from the heads of weight-1 edges leaving . On a shortest path to , the part before its last weight-1 edge is itself shortest, with cost . The algorithm is a breadth-first search over these levels.
Definition 16.2.2
(Snapshot, stale entry and settled vertex)
A deque entry is a snapshot: the value of at the moment the entry was inserted. It is stale when is already settled or . A vertex is settled when a non-stale entry for it is removed from the front; its label is never changed afterwards.
Why the deque is ordered
Lemma 16.2.3
(Two-key invariant of the deque)
At the beginning of every removal step, the keys stored in the deque, stale or live, are in nondecreasing order from front to back, and for some integer every stored key is or .
Proof
(Induction on removal steps)
At the beginning of each removal, stored keys are in nondecreasing order and span at most one: for some integer , every stored key is either or . Initially the sole key is zero. Removing the front, including removing a stale entry, preserves the statement for what remains. If a live entry of key is processed, every successful zero-edge relaxation inserts key at the front, while every successful one-edge relaxation inserts key at the back. The order and span therefore remain valid. This argument concerns all stored keys, stale or live; the stale check decides whether to scan edges, not where an entry sits.
Why settling is safe
Theorem 16.2.4
(Settled labels are exact)
If all weights lie in , then each vertex satisfies at the moment it is settled. At termination for every vertex , with for unreachable ones.
Proof
(First unsettled vertex on a shortest path)
We prove by induction that every settled vertex has its true minimum distance. The first settled vertex is , with distance zero. Suppose the next live removal settles with key , and all earlier settled vertices are correct. Its label is a walk cost, so . If , choose a shortest path to and its first vertex not yet settled. Its predecessor is settled. The prefix to has cost ; otherwise a cheaper prefix would give a cheaper walk to . When was processed, its edge to either set or preserved a label at most the path's prefix cost to . A finite label is itself a walk cost, so it cannot be below ; hence the current label of is .
There are two cases. If , then , contradicting the live-entry check . If , its most recent strict improvement left a current snapshot in the deque: a current snapshot cannot have been removed earlier without settling , and the entry just removed belongs to . Its key is less than , contradicting the deque ordering when was removed. Thus . The induction also justifies skipping relaxations into settled vertices. Every reachable vertex is eventually settled: if one were not, an edge on a path from the settled region to an unsettled reachable vertex would have inserted a live finite entry, contradicting termination. Unreachable labels remain infinite because only actual walks create finite labels.
Proof X-ray
Which two facts collide in the proof
The proof compares the removed entry with the first unsettled vertex on a shortest path to . Induction on the predecessor gives , and the cost of the rest of the path, which is at least , gives . The invariant of the previous lemma says that no stored key can lie in front of the key of the removed front entry, so a current snapshot of with a smaller key cannot exist. The case is the same collision with the live-entry test . Weights in are used only inside the invariant: a weight edge could place a smaller key behind a larger one, which is exactly the failure shown in the counterexample below.
Worked trace: an entry becomes stale
Worked example 16.2.5
(An entry becomes stale)
Take edges, in the displayed adjacency order, of weight 1, of weight 0; of weight 0, of weight 1; of weight 1, of weight 0; and of weight 0. Pairs are (key,vertex) and the left end is the front.
| Removed | Action | Deque after action |
|---|---|---|
| settle; discover | ||
| settle; improve to 0, discover | ||
| settle; discover | ||
| settle; improve to 0 | ||
| settle | ||
| skip stale/settled | ||
| skip stale/settled |
All five distances are zero: for example has cost zero. The old entries and are not errors; they are snapshots that became obsolete. In contrast, marking permanently visited as soon as the direct edge discovers it would prevent the improvement through .
Worked example 16.2.6
(A self-loop and an unreachable vertex)
Take vertices and edges of weight and of weight , in that order; has no incoming edge. Remove and settle . The self-loop is skipped because is already settled, and the edge to gives and the entry at the back. Removing settles , and the deque is empty. The output is for : the loop changes nothing, and keeps because only real walks create finite labels.
Worked example 16.2.7
(A cycle of zero-weight edges)
Take edges (0), (0), (0), (1). Remove : goes to the front. Remove : goes to the front. Remove : the edge back to is skipped because is settled, and goes to the back. Removing settles . The distances are for . The zero cycle costs nothing to ignore: settled vertices are never relaxed into, so it cannot make the loop run forever.
Complexity and contract
Proposition 16.2.8
(Cost of 0–1 BFS)
Let and let count directed adjacency entries. The algorithm inserts at most deque entries, runs in time, and uses auxiliary space.
Proof
(Counting scans and insertions)
Let and , counting each directed adjacency entry. Initialization costs . A vertex is settled once, so each outgoing entry is scanned at most once. Each successful strict relaxation corresponds to an edge scan and inserts one pair; there are at most such insertions plus the initial pair. Deque operations, including stale removals, total . Time is under the stated constant-time arithmetic and deque model, including empty-edge graphs. Arrays use and the deque can contain snapshots, so auxiliary space is for this explicit implementation, excluding the graph representation.
The proof does not apply unchanged to weight 2 or negative weights: the two-key invariant or the settled-label proof can fail. Zero-weight cycles are harmless for minimum distances, but can create infinitely many equal-cost walks. This algorithm computes distances, not the number of shortest walks.
Counterexample mode
A weight-2 edge breaks the deque order
Claim: the same algorithm, pushing every edge of positive weight to the back, also works for weights in . Take edges, in this adjacency order, (2), (1), (0). Removing gives and , so the deque is , which is out of order. Removing settles with label . Then is removed, and the edge is ignored because is settled. The output is wrong: costs . The repair is to keep weights in , or to use Dijkstra's algorithm with a heap for general nonnegative weights.
Common mistakes
Common mistake
(Fewest edges is not lowest cost)
A direct edge of weight uses one edge, while a detour of two zero-weight edges costs . Plain BFS, which orders vertices by edge count, would report the direct edge, and in the trace above it would give instead of .
Common mistake
(Marking a vertex visited when it is discovered)
A label found by a weight- edge can still be improved through a zero-weight detour that is processed later. Marking settled as soon as the edge discovers it would block the improvement through . Settle only when a non-stale entry is removed from the front.
Checklist
- State directed or undirected adjacency conventions, , and weights in .
- Push weight 0 to the front and weight 1 to the back; retain the key snapshot.
- Skip stale or settled entries, and settle on removal rather than first discovery.
- Prove both deque ordering and shortest-distance correctness; distinguish them.
- Count edge scans and queued snapshots; include initialization and empty graphs.
Exercises
Quick check
(Run the algorithm on the edges (1), (1), (0), (0), in this adjacency order. Give the deque after each removal and the final distances.)
Pairs are (key, vertex) and the left end is the front.
Solution · Answer
Remove : and go to the back, giving . Remove : settle ; the weight-0 edge gives at the front, so . Remove : settle , giving . Remove : settle ; the edge to is skipped, giving . The distances are for .
Quick check
(Edges, in this order: (1), (0), (0). Suppose the weight-0 improvement is pushed to the back instead of the front. What does the algorithm output for , and what is ?)
Write the deque after removing .
Solution · Answer
Removing gives at the back, and then pushed to the back too: . The out-of-order entry is removed first and settles with label ; the later edge is ignored. The output is , but through . Putting zero-cost improvements at the front keeps the smaller key in front.
Quick check
(The graph is undirected with edges, each of weight or . What is the value of in the bound ?)
Recall how an undirected edge is stored.
Solution · Answer
Each undirected edge contributes two directed adjacency entries, so . The bound is therefore , but the number of deque insertions can reach .