Why does BFS find the minimum-hop route in an unweighted network, and when does that guarantee break?
answer
- think about the order nodes leave the queue
- what does first-in-first-out enforce about distances
- the frontier holds only two adjacent distances
- first arrival is final only under uniform cost
- fewest links is not lowest latency
basics
~20 sBFS expands nodes strictly in order of hop count, so the first time it reaches a node it has used the fewest possible hops. The guarantee holds only while every edge costs the same; unequal edge costs break it.
solid answer
~50 sBFS keeps a first-in-first-out frontier, so it drains everything one hop away before anything two hops away. That ordering is the whole proof: distances come out of the queue non-decreasing, so the first arrival at a node is a minimum-hop arrival and can never be improved later. On a network topology where a link is a link — routers connected by cables you count, not time — that is exactly the minimum-hop route. The moment links carry unequal costs, say one hop over a saturated 1 Gbps trunk versus three hops over idle fibre, the claim collapses: BFS still returns the fewest links, but fewest links is no longer lowest latency. Uniform cost is the precondition; if all edges cost the same non-zero constant, BFS is still right, because the cheapest path is just hops times that constant.
go deeper
Be ready to state, unprompted, that the shortest-path claim is about hop counts on equal-cost edges. Recall that the queue drains one layer before starting the next, and that a node's distance is fixed the first time it is discovered.
Explain the mechanism: the frontier holds at most two consecutive distances, so distances leave the queue non-decreasing and first arrival is optimal. Show where that argument uses the uniform-cost assumption and what fails without it.
Demonstrate that you check the precondition before reaching for the algorithm. Given a topology, ask what an edge actually represents — a link you count or a latency you sum — and say plainly when minimum-hop is the wrong objective even though it is cheap to compute.
Own the framing decision: whether the system should model routes as unweighted at all. Uniform-cost modelling buys a linear-time answer and simple operations; adding real per-link costs buys accuracy at the price of a heavier algorithm, tuning and freshness requirements on the cost data.
## The claim, stated precisely BFS on a graph whose edges all count the same returns, for every reachable node, a path with the **fewest edges**. It does not return a cheapest path in any other sense, and the difference between those two sentences is where most candidates lose the question. ## Why the queue discipline is the proof BFS keeps a frontier in a first-in-first-out queue. The source goes in at distance 0. Every time a node is removed, its undiscovered neighbours are appended at distance one greater. Two properties follow, and together they are the whole argument: 1. **The queue is non-decreasing in distance.** At any moment the queue holds nodes of at most two consecutive distances, `d` and `d+1`. You only ever append `d+1` entries while draining `d` entries, so nothing of distance `d+2` can appear before the last `d` is gone. 2. **First arrival is minimum arrival.** Suppose some node `x` were truly reachable in `k` hops but BFS first reached it at distance `k+1`. Walk the true `k`-hop path backwards: its second-to-last node `y` sits at true distance `k-1`. By induction BFS discovered `y` at distance `k-1`, and when `y` was drained it looked at every neighbour, including `x`. So `x` was either already discovered (at distance `≤ k`) or discovered right then at `k`. Either way, not `k+1`. Contradiction. That induction is worth being able to say out loud; it is the difference between "BFS gives shortest paths" as a memorised slogan and as a fact you can defend. ## The precondition, and how interviewers break it The induction used one assumption and one only: **every edge advances the distance by the same amount**. Concretely: - **All edges cost 1** — BFS is exact. - **All edges cost the same constant `c`** — BFS is still exact; the answer is `c` times the hop count. Candidates often think a uniform non-unit weight breaks BFS. It does not. - **Edges cost different amounts** — BFS is no longer a shortest-path algorithm for cost. It is still a correct *minimum-hop* algorithm, which may be exactly what you want ("how many router hops away is this host?") or completely wrong ("which route has the lowest latency?"). This is the standard trap in a network-topology framing. A candidate says "BFS finds shortest paths", the interviewer adds per-link latency to the diagram, and the candidate keeps the same answer. The correct move is to notice that the queue's non-decreasing property is what died: with unequal costs, a node can be reached later along a cheaper route, so first arrival is no longer final. Once first arrival stops being final you need a structure that can revisit and improve — which is where the weighted shortest-path family begins, and where plain BFS ends. ## Directedness, and other things that do *not* break it Several perfectly ordinary conditions leave the guarantee intact, and knowing which ones is the sign that you understand the proof rather than the slogan: - **Directed edges.** BFS follows out-edges only; the induction never assumed symmetry. Minimum-hop distance from the source is still correct (it simply is not symmetric any more). - **Cycles.** The visited marking makes each node enter the frontier once; cycles cost nothing extra. - **Disconnected regions.** Nodes never reached simply have no finite distance — that is an answer, not a failure. - **Multiple minimum-hop routes.** Ties are normal. BFS finds one of them, determined by the order neighbours are listed. If you need all of them, you record every discoverer at the minimum distance instead of one. ## Cost BFS touches each node once and scans each node's neighbour list once, giving **O(V + E)** time — linear in the size of the graph, not in the number of paths. Space is dominated by the visited marking, O(V), plus the frontier, which is bounded by the widest layer. On a wide, shallow topology the frontier can hold a large fraction of the nodes at once; that is BFS's characteristic memory profile and the reason it is not free on very wide graphs. ## What to actually say in the room "BFS drains the frontier in hop order, so distances come off the queue non-decreasing and the first time you touch a node you have touched it optimally — but only because every edge advances the count by the same amount. Give the links unequal costs and fewest-hops stops meaning cheapest, and I need something that can revisit a node when a cheaper route shows up."
- If every link in the topology cost 5 units instead of 1, would BFS still return the cheapest route?Yes. The proof only needs every edge to advance the distance by the *same* amount, not by exactly one. With a uniform constant cost the cheapest route is simply the fewest-hop route scaled by that constant, so BFS is exact and you multiply the hop count at the end. Uniformity is the precondition, not unit weight.
- Does the minimum-hop guarantee survive on a directed topology?Yes. BFS follows out-edges only, and the inductive argument never assumed edges were symmetric. You get correct minimum-hop distances *from* the source along directed links. What you lose is symmetry: the distance from the source to a node says nothing about the distance back, so a second traversal on the reversed edges is needed if you want that.
- A few links cost zero and the rest cost one. Can you still keep a queue-based traversal?Yes, with a modified discipline: a double-ended frontier where a zero-cost neighbour is inserted at the front and a unit-cost neighbour at the back, which preserves the non-decreasing property that plain first-in-first-out gave you. Anything richer than a tiny fixed cost set leaves this leaf's territory and belongs to the weighted shortest-path algorithms.
saying these in an interview costs you the question
- Says BFS finds shortest paths without naming the uniform-cost precondition
- Thinks a uniform non-unit edge cost breaks BFS
- Claims BFS handles weighted edges if you drain layer by layer
- Believes a shorter route to an already-visited node can appear later
- Confuses the fewest-hop route with the lowest-latency route
- Thinks BFS needs an undirected graph to be correct