Skip to main content

BFS and Unweighted Shortest Paths

What This Concept Is​

BFS discovers vertices in nondecreasing hop distance from a source using a FIFO queue. Mark a vertex discovered when it is enqueued, set its distance once, and record the edge used to discover it. Under adjacency lists, initialization plus traversal costs O(V+E); queue/distance/parent state costs O(V), with representation storage additional if constructed inside the function.

Why It Matters Here​

The queue discipline supports a shortest-hop proof. A stack may find reachability but does not retain the level argument. A BFS tree is one witness among possibly many shortest-hop trees, so tests should validate distances and paths rather than insist on one adjacency-order-dependent parent array.

Concrete Examples​

For edges 0→1,0→2,1→3,2→3 and isolated 4, source 0 has distances [0,1,1,2,None]. Either incoming edge can parent vertex 3. Marking only on dequeue may enqueue 3 twice and can overwrite witnesses or inflate the frontier.

Proof: source distance 0 is correct. When a vertex at level k scans an undiscovered neighbor, it gives a path of length k+1. A shorter route would have had a predecessor at an earlier level, already scanned, contradicting undiscovered status. FIFO preserves this level ordering through each enqueue. Self-loops and parallel edges do not require a new vertex visit.

Common Confusion / Misconceptions​

BFS minimizes number of edges, not arbitrary edge-weight sums. For 0→1 of weight 10 and 0→2→1 with weights 1,1, it prefers one hop but not minimum cost. Using a list's front-removal operation can add linear queue shifts; use a real queue. Stopping at target discovery is safe for a single hop distance/path, but does not produce a complete all-vertices result.

How To Use It​

Define unreachable distance and source parent explicitly. Multi-source BFS initializes every source at distance zero before traversal, yielding distance to the nearest source in hops. Reverse edges first if the question is distance from every vertex to one target in a directed graph.

Check Yourself​

  1. Why mark on enqueue?
  2. Which proof step needs equal edge cost?
  3. Why can two different parent arrays both be correct?
  4. How does multi-source initialization change the question?

Mini Drill or Application​

Implement Lab A and reconstruct a path using original edge IDs. Check endpoint continuity, path length, source termination and unreachable status. Change one edge weight to make the cheapest route use more hops; explain why the BFS result remains correct for its own contract. See P5.

Read This Only If Stuck​

Find breadth-first search and shortest-hop proofs in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.