Shortest Path (Unweighted) - Learning Module

Loading content...

0/276

Why BFS Works for This

Beyond "It Just Works"

Throughout this module, we've asserted that BFS finds shortest paths in unweighted graphs. We've shown how it works, but truly understanding why requires looking beneath the surface at the fundamental properties that make this guaranteed.

This isn't mere academic curiosity. Understanding the why is essential for:

Knowing when you CAN use BFS (unweighted or unit-weight edges)
Knowing when you CANNOT use BFS (weighted edges with different costs)
Adapting BFS to novel problems (recognizing the invariants that must hold)
Debugging when things go wrong (identifying which property was violated)

What You Will Learn

By the end of this page, you will understand the deep theoretical foundation of BFS shortest paths: the FIFO invariant, the level-order lemma, the formal proof of correctness, and why the same approach fails catastrophically for weighted graphs. You'll develop the reasoning skills to recognize when BFS applies and when it doesn't.

The Core Insight: FIFO Preserves Level Order

The entire correctness of BFS for shortest paths rests on a single elegant insight:

In a FIFO queue, if all items of level k are added before any item of level k+1, then all items of level k will be processed before any item of level k+1.

This sounds almost trivially true, but its implications are profound. Let's trace through exactly why this matters for shortest paths.

How BFS Maintains Level Order:

We start with the source at level 0 in the queue: [s]
We process s and add all its neighbors (level 1 vertices) to the queue
- Queue after: [a, b, c] (all level 1)
We process a (first level 1 vertex) and add its new neighbors (level 2)
- Queue after: [b, c, d, e] (level 1, level 1, level 2, level 2)
We process b (second level 1 vertex) and add its new neighbors
- Queue continues to maintain order...

Critical observation: When we process a level-k vertex, we add level-(k+1) vertices to the back of the queue. All remaining level-k vertices are still ahead in the queue. Therefore, level-(k+1) vertices are processed only after ALL level-k vertices.

FIFO is the Key

Replace the queue with a stack (LIFO), and this property breaks. With a stack, the most recently added vertices are processed first—which could be vertices at deeper levels. This is exactly what happens in DFS: we dive deep before exploring breadth, destroying the level-order guarantee.

Formal Statement (Level-Order Lemma):

During BFS from source s, let d(v) denote the length of the shortest path from s to v. The queue at any point contains vertices at most two consecutive distance levels: all vertices with distance k, followed by some vertices with distance k+1, for some k ≥ 0.

This lemma captures the queue's structure: it's always "stratified" by distance. We never have a jumbled mix of near and far vertices.

Formal Proof of Correctness

Let's prove rigorously that BFS computes correct shortest path distances.

Theorem: For any vertex v reachable from source s in an unweighted graph, BFS assigns distance[v] = d(s, v), where d(s, v) is the true shortest path length from s to v.

Proof by Strong Induction:

Base Case (k = 0):

The only vertex at distance 0 from s is s itself.
BFS initializes distance[s] = 0. ✓

Inductive Hypothesis:

Assume that for all vertices u with d(s, u) ≤ k, BFS correctly assigns distance[u] = d(s, u).

Inductive Step (proving for k+1):

Let v be any vertex with d(s, v) = k+1.
By definition of shortest path, there exists a path s → ... → u → v where d(s, u) = k.
By the inductive hypothesis, BFS correctly assigns distance[u] = k.
When BFS processes u, it examines all neighbors of u, including v.
Case 1: v has not been visited yet.
- BFS assigns distance[v] = distance[u] + 1 = k + 1. ✓
Case 2: v has already been visited (distance[v] already set).
- v was discovered from some vertex w with distance[w] = distance[v] - 1.
- By Level-Order Lemma, w was processed before or at the same time as u.
- Therefore, distance[w] ≤ k, so distance[v] ≤ k + 1.
- But d(s, v) = k + 1 is the minimum, so distance[v] ≥ k + 1.
- Therefore, distance[v] = k + 1. ✓

Conclusion: By induction, BFS correctly computes shortest path distances for all reachable vertices. ∎

The Proof's Structure

This proof relies on three properties: (1) BFS processes vertices in level order, (2) when a vertex is first discovered, it's discovered from a vertex one level closer, and (3) subsequent discoveries can only be from vertices at the same or later levels. The FIFO queue guarantees all three.

Why It Breaks for Weighted Graphs

Understanding why BFS fails for weighted graphs illuminates what makes it work for unweighted graphs.

The Problem:

In a weighted graph, edges have different costs. A path through more edges might have lower total cost than a path through fewer edges.

Example:

Converting Mermaid diagram...

What BFS Would Do:

Start at S, distance = 0
Process S, discover A (1 hop) and B (1 hop)
Queue: [A, B], both at "distance 1"
Process A first (or B, depending on order)
BFS thinks: shortest path to A is S→A with 1 hop

The Truth:

Path S→A: 1 hop, but cost = 10
Path S→B→C→A: 3 hops, but cost = 1+1+1 = 3

The 3-hop path is cheaper! BFS found the path with fewer edges, but not the path with lower cost.

Why the Proof Breaks:

Our proof relied on the fact that discovering a vertex v from a closer vertex u means v's distance is exactly d(u) + 1. In weighted graphs, "closer in hops" doesn't mean "closer in cost." The Level-Order Lemma still holds (for hop count), but hop count ≠ path cost.

Different Metrics, Different Algorithms

BFS minimizes hop count. Dijkstra's minimizes total edge weight. Bellman-Ford handles negative weights. Each algorithm is correct for its specific metric. Using the wrong algorithm gives wrong answers.

The "Unit Weight" Condition

BFS works whenever all edges have the same weight (not necessarily 1, just equal). This is called the "unit weight" or "uniform weight" condition.

Why Equal Weights Suffice:

If all edges have weight w (for any positive w), then:

Total cost of a k-edge path = k × w
Minimizing k automatically minimizes total cost
BFS minimizes k, so it minimizes total cost

Example:

If all edges cost 7, a 3-edge path costs 21, and a 5-edge path costs 35. The fewer-hop path is always cheaper.

General Principle:

When all actions have equal cost, the fewest-action solution IS the minimum-cost solution.

This is why BFS works for:

Mazes (each step costs 1)
Word ladders (each transformation costs 1)
Social network distance (each friendship is 1 hop)
Puzzle solving (each move counts equally)

The "-1 BFS" Variant:

For graphs with edge weights 0 or 1 only, a modified BFS called "0-1 BFS" works in O(V + E):

Use a deque (double-ended queue) instead of regular queue
When following a 0-weight edge: add to front (these vertices are same distance)
When following a 1-weight edge: add to back (these are 1 further)

This maintains the level-order invariant even with mixed 0/1 weights.

zero_one_bfs
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 0-1 BFS: Works when all edge weights are 0 or 1
function zeroOneBFS(
    graph: Map<number, Array<{neighbor: number; weight: 0 | 1}>>,
    source: number
): Map<number, number> {
    const distance = new Map<number, number>();
    const deque: number[] = [];  // Use as double-ended queue
    
    distance.set(source, 0);
    deque.push(source);
    
    while (deque.length > 0) {
        const current = deque.shift()!;  // Pop front
        const currentDist = distance.get(current)!;
        
        for (const {neighbor, weight} of graph.get(current) || []) {
            const newDist = currentDist + weight;
            
            if (!distance.has(neighbor) || newDist < distance.get(neighbor)!) {
                distance.set(neighbor, newDist);
                
                if (weight === 0) {
                    deque.unshift(neighbor);  // Add to FRONT
                } else {
                    deque.push(neighbor);     // Add to BACK
                }
            }
        }
    }
    
    return distance;
}
 
// This maintains level-order:
// - 0-weight neighbors are at same level → front of deque
// - 1-weight neighbors are at next level → back of deque

Connecting to Dijkstra's Algorithm

Understanding BFS for unweighted graphs helps understand Dijkstra's algorithm for weighted graphs.

The Key Difference:

Aspect	BFS	Dijkstra's
Edge weights	All equal	Variable (non-negative)
Queue type	FIFO queue	Priority queue (min-heap)
Processing order	By hop count	By tentative distance
Relaxation	Never (first discovery is final)	May happen (shorter path found later)

Why Dijkstra's Needs a Priority Queue:

In weighted graphs, a vertex discovered later might have a shorter total distance. We can't rely on discovery order. Instead, we always process the vertex with the smallest tentative distance—guaranteed by a priority queue.

BFS as a Special Case:

BFS is actually Dijkstra's algorithm where all edges have weight 1:

Priority queue degrades to FIFO queue (all same-level vertices have same priority)
No relaxation needed (hop count discovery order = distance order)
O((V + E) log V) simplifies to O(V + E) (no heap operations needed)

Conceptual Insight:

BFS works because with unit weights, the FIFO queue automatically maintains priority order. Vertices with distance k all have the same priority (k), and they're all added before vertices with distance k+1. The FIFO queue is a "free" priority queue when priorities come in ascending order.

When weights vary, priorities are no longer in order, and we need an explicit priority queue to process vertices in correct order.

The Simplicity of Equal Weights

When problem constraints guarantee equal edge weights, always use BFS over Dijkstra's: it's simpler, faster (O(V+E) vs O((V+E) log V)), and less error-prone. Recognizing this is a valuable optimization skill.

The Invariants That Make BFS Work

Let's enumerate the key invariants that hold throughout BFS execution. These invariants are the "contracts" that guarantee correctness.

BFS Loop Invariants

•Invariant 1: Correct distances for visited vertices. For every vertex v in the visited set, distance[v] equals the true shortest path length from source to v.
•Invariant 2: Queue ordering. The queue contains vertices at most two distance levels k and k+1, with all level-k vertices before all level-(k+1) vertices.
•Invariant 3: Frontier completeness. For every unvisited vertex v, if there's an edge (u, v) where u is visited and at distance k, then v is in the queue at distance k+1 (or already visited).
•Invariant 4: Distance monotonicity. Distances assigned during BFS are non-decreasing: we never assign a distance smaller than any previously assigned distance.
•Invariant 5: First discovery finality. Once a vertex is marked visited and assigned a distance, that assignment never changes.

Verifying Invariants:

Initialization: Before the main loop, only the source is visited with distance 0. All invariants hold trivially.

Maintenance: Each iteration:

Dequeues a vertex at the current minimum level (Invariant 2)
Visits neighbors not yet visited, assigning distance = current + 1 (Invariants 1, 4, 5)
Adds new vertices to back of queue (Invariant 2 preserved)
Marks new vertices visited (Invariant 3)

Termination: When the queue empties, all reachable vertices have been assigned correct distances.

Why Invariants Matter

Loop invariants are the formal tool for proving algorithm correctness. If you can show: (1) invariants hold initially, (2) each iteration preserves them, and (3) invariants imply the desired result, you've proven correctness. This is how we rigorously verify BFS works.

Common Misconceptions

Let's address common misunderstandings about BFS and shortest paths.

Misconceptions

•"BFS always finds shortest paths"
•"DFS can find shortest paths too"
•"Mark visited when processing"
•"BFS only works on trees"
•"Priority queue makes BFS faster"

Corrections

•Only for unweighted (equal-weight) graphs
•DFS makes no distance guarantees; it's fundamentally wrong for shortest paths
•Mark visited when ADDING to queue, not when processing (prevents duplicates)
•BFS works on any graph; cycles handled by visited set
•Priority queue is unnecessary; FIFO queue gives same result faster

Detailed Misconception: "Mark Visited When Processing"

This is a subtle but important error:

Incorrect:

while queue:
    current = queue.popleft()
    visited.add(current)  # WRONG: too late!
    for neighbor in graph[current]:
        if neighbor not in visited:
            queue.append(neighbor)

Problem: A vertex might be added to the queue multiple times before being processed, wasting time and potentially causing issues.

Correct:

while queue:
    current = queue.popleft()
    for neighbor in graph[current]:
        if neighbor not in visited:
            visited.add(neighbor)  # RIGHT: mark immediately
            queue.append(neighbor)

Key Insight: Mark visited at discovery time (when adding to queue), not processing time (when dequeuing). This ensures each vertex is added exactly once.

When to Use (and Not Use) BFS

Armed with deep understanding of why BFS works, you can make informed decisions about algorithm selection.

Algorithm Selection Guide
Scenario	Algorithm	Why
Unweighted graph, shortest path	BFS	O(V+E), simple, correct
All edges weight 1	BFS	Same as unweighted
All edges same positive weight	BFS	Minimizing hops = minimizing cost
Variable non-negative weights	Dijkstra's	Need priority queue for correct ordering
Negative weights (no negative cycles)	Bellman-Ford	Dijkstra's fails with negative weights
All-pairs shortest paths	Floyd-Warshall or repeated Dijkstra's	Depends on graph density
Edge weights 0 or 1 only	0-1 BFS	O(V+E) with deque trick
Just need any path (not shortest)	BFS or DFS	Both work; DFS may be simpler
Need shortest path AND minimum cost	Check if weights equal	If equal: BFS. Otherwise: Dijkstra's

The Decision Process

Ask these questions in order: (1) Are all edge weights equal? If yes, use BFS. (2) Are all edges non-negative? If yes, use Dijkstra's. (3) Are there negative edges? Use Bellman-Ford. (4) Need all pairs? Consider Floyd-Warshall. This flowchart handles most shortest path scenarios.

Summary: Why BFS Works

Let's consolidate the deep understanding we've developed:

Key Takeaways

•FIFO queue preserves level order — Vertices at distance k are all processed before any at distance k+1
•First discovery is optimal — The queue ordering means the first path to any vertex is the shortest
•Inductive proof of correctness — Strong induction on distance proves BFS assigns correct distances
•Unit weight condition — BFS works when all edges have equal cost (not just weight 1)
•Fails for variable weights — Different edge costs break the "first discovery = optimal" property
•BFS is simplified Dijkstra's — With equal weights, priority queue degrades to FIFO queue
•Loop invariants guarantee correctness — Formal verification via invariant maintenance
•Algorithm selection — Match algorithm to weight structure: BFS, Dijkstra's, Bellman-Ford, etc.

Module Complete:

You now have a complete, rigorous understanding of shortest paths in unweighted graphs using BFS:

Why BFS finds shortest paths — The level-order property and optimality theorem
Parent tracking — Reconstructing the actual path, not just its length
Distance array — Efficient distance queries and multi-source BFS
Deep theoretical foundation — Invariants, proofs, and algorithm selection

This foundation prepares you for weighted shortest path algorithms (Dijkstra's, Bellman-Ford) in subsequent modules, where you'll see how the same conceptual framework extends to more complex scenarios.

Module Complete

Congratulations! You've mastered shortest paths in unweighted graphs using BFS. You understand not just the algorithm mechanics, but the deep theoretical reasons why it works. This foundation will serve you well as you progress to weighted shortest path algorithms and more advanced graph techniques.

Why BFS Works for This

Beyond "It Just Works"

This isn't mere academic curiosity. Understanding the why is essential for:

Knowing when you CAN use BFS (unweighted or unit-weight edges)
Knowing when you CANNOT use BFS (weighted edges with different costs)
Adapting BFS to novel problems (recognizing the invariants that must hold)
Debugging when things go wrong (identifying which property was violated)

What You Will Learn

The Core Insight: FIFO Preserves Level Order

The entire correctness of BFS for shortest paths rests on a single elegant insight:

In a FIFO queue, if all items of level k are added before any item of level k+1, then all items of level k will be processed before any item of level k+1.

This sounds almost trivially true, but its implications are profound. Let's trace through exactly why this matters for shortest paths.

How BFS Maintains Level Order:

We start with the source at level 0 in the queue: [s]
We process s and add all its neighbors (level 1 vertices) to the queue
- Queue after: [a, b, c] (all level 1)
We process a (first level 1 vertex) and add its new neighbors (level 2)
- Queue after: [b, c, d, e] (level 1, level 1, level 2, level 2)
We process b (second level 1 vertex) and add its new neighbors
- Queue continues to maintain order...

FIFO is the Key

Formal Statement (Level-Order Lemma):

This lemma captures the queue's structure: it's always "stratified" by distance. We never have a jumbled mix of near and far vertices.

Formal Proof of Correctness

Let's prove rigorously that BFS computes correct shortest path distances.

Theorem: For any vertex v reachable from source s in an unweighted graph, BFS assigns distance[v] = d(s, v), where d(s, v) is the true shortest path length from s to v.

Proof by Strong Induction:

Base Case (k = 0):

The only vertex at distance 0 from s is s itself.
BFS initializes distance[s] = 0. ✓

Inductive Hypothesis:

Assume that for all vertices u with d(s, u) ≤ k, BFS correctly assigns distance[u] = d(s, u).

Inductive Step (proving for k+1):

Let v be any vertex with d(s, v) = k+1.
By definition of shortest path, there exists a path s → ... → u → v where d(s, u) = k.
By the inductive hypothesis, BFS correctly assigns distance[u] = k.
When BFS processes u, it examines all neighbors of u, including v.
Case 1: v has not been visited yet.
- BFS assigns distance[v] = distance[u] + 1 = k + 1. ✓
Case 2: v has already been visited (distance[v] already set).
- v was discovered from some vertex w with distance[w] = distance[v] - 1.
- By Level-Order Lemma, w was processed before or at the same time as u.
- Therefore, distance[w] ≤ k, so distance[v] ≤ k + 1.
- But d(s, v) = k + 1 is the minimum, so distance[v] ≥ k + 1.
- Therefore, distance[v] = k + 1. ✓

Conclusion: By induction, BFS correctly computes shortest path distances for all reachable vertices. ∎

The Proof's Structure

Why It Breaks for Weighted Graphs

Understanding why BFS fails for weighted graphs illuminates what makes it work for unweighted graphs.

The Problem:

In a weighted graph, edges have different costs. A path through more edges might have lower total cost than a path through fewer edges.

Example:

Converting Mermaid diagram...

What BFS Would Do:

Start at S, distance = 0
Process S, discover A (1 hop) and B (1 hop)
Queue: [A, B], both at "distance 1"
Process A first (or B, depending on order)
BFS thinks: shortest path to A is S→A with 1 hop

The Truth:

Path S→A: 1 hop, but cost = 10
Path S→B→C→A: 3 hops, but cost = 1+1+1 = 3

The 3-hop path is cheaper! BFS found the path with fewer edges, but not the path with lower cost.

Why the Proof Breaks:

Different Metrics, Different Algorithms

The "Unit Weight" Condition

BFS works whenever all edges have the same weight (not necessarily 1, just equal). This is called the "unit weight" or "uniform weight" condition.

Why Equal Weights Suffice:

If all edges have weight w (for any positive w), then:

Total cost of a k-edge path = k × w
Minimizing k automatically minimizes total cost
BFS minimizes k, so it minimizes total cost

Example:

If all edges cost 7, a 3-edge path costs 21, and a 5-edge path costs 35. The fewer-hop path is always cheaper.

General Principle:

When all actions have equal cost, the fewest-action solution IS the minimum-cost solution.

This is why BFS works for:

Mazes (each step costs 1)
Word ladders (each transformation costs 1)
Social network distance (each friendship is 1 hop)
Puzzle solving (each move counts equally)

The "-1 BFS" Variant:

For graphs with edge weights 0 or 1 only, a modified BFS called "0-1 BFS" works in O(V + E):

Use a deque (double-ended queue) instead of regular queue
When following a 0-weight edge: add to front (these vertices are same distance)
When following a 1-weight edge: add to back (these are 1 further)

This maintains the level-order invariant even with mixed 0/1 weights.

zero_one_bfs
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 0-1 BFS: Works when all edge weights are 0 or 1
function zeroOneBFS(
    graph: Map<number, Array<{neighbor: number; weight: 0 | 1}>>,
    source: number
): Map<number, number> {
    const distance = new Map<number, number>();
    const deque: number[] = [];  // Use as double-ended queue
    
    distance.set(source, 0);
    deque.push(source);
    
    while (deque.length > 0) {
        const current = deque.shift()!;  // Pop front
        const currentDist = distance.get(current)!;
        
        for (const {neighbor, weight} of graph.get(current) || []) {
            const newDist = currentDist + weight;
            
            if (!distance.has(neighbor) || newDist < distance.get(neighbor)!) {
                distance.set(neighbor, newDist);
                
                if (weight === 0) {
                    deque.unshift(neighbor);  // Add to FRONT
                } else {
                    deque.push(neighbor);     // Add to BACK
                }
            }
        }
    }
    
    return distance;
}
 
// This maintains level-order:
// - 0-weight neighbors are at same level → front of deque
// - 1-weight neighbors are at next level → back of deque

Connecting to Dijkstra's Algorithm

Understanding BFS for unweighted graphs helps understand Dijkstra's algorithm for weighted graphs.

The Key Difference:

Aspect	BFS	Dijkstra's
Edge weights	All equal	Variable (non-negative)
Queue type	FIFO queue	Priority queue (min-heap)
Processing order	By hop count	By tentative distance
Relaxation	Never (first discovery is final)	May happen (shorter path found later)

Why Dijkstra's Needs a Priority Queue:

BFS as a Special Case:

BFS is actually Dijkstra's algorithm where all edges have weight 1:

Priority queue degrades to FIFO queue (all same-level vertices have same priority)
No relaxation needed (hop count discovery order = distance order)
O((V + E) log V) simplifies to O(V + E) (no heap operations needed)

Conceptual Insight:

When weights vary, priorities are no longer in order, and we need an explicit priority queue to process vertices in correct order.

The Simplicity of Equal Weights

The Invariants That Make BFS Work

Let's enumerate the key invariants that hold throughout BFS execution. These invariants are the "contracts" that guarantee correctness.

BFS Loop Invariants

•Invariant 1: Correct distances for visited vertices. For every vertex v in the visited set, distance[v] equals the true shortest path length from source to v.
•Invariant 2: Queue ordering. The queue contains vertices at most two distance levels k and k+1, with all level-k vertices before all level-(k+1) vertices.
•Invariant 3: Frontier completeness. For every unvisited vertex v, if there's an edge (u, v) where u is visited and at distance k, then v is in the queue at distance k+1 (or already visited).
•Invariant 4: Distance monotonicity. Distances assigned during BFS are non-decreasing: we never assign a distance smaller than any previously assigned distance.
•Invariant 5: First discovery finality. Once a vertex is marked visited and assigned a distance, that assignment never changes.

Verifying Invariants:

Initialization: Before the main loop, only the source is visited with distance 0. All invariants hold trivially.

Maintenance: Each iteration:

Dequeues a vertex at the current minimum level (Invariant 2)
Visits neighbors not yet visited, assigning distance = current + 1 (Invariants 1, 4, 5)
Adds new vertices to back of queue (Invariant 2 preserved)
Marks new vertices visited (Invariant 3)

Termination: When the queue empties, all reachable vertices have been assigned correct distances.

Why Invariants Matter

Common Misconceptions

Let's address common misunderstandings about BFS and shortest paths.

Misconceptions

•"BFS always finds shortest paths"
•"DFS can find shortest paths too"
•"Mark visited when processing"
•"BFS only works on trees"
•"Priority queue makes BFS faster"

Corrections

•Only for unweighted (equal-weight) graphs
•DFS makes no distance guarantees; it's fundamentally wrong for shortest paths
•Mark visited when ADDING to queue, not when processing (prevents duplicates)
•BFS works on any graph; cycles handled by visited set
•Priority queue is unnecessary; FIFO queue gives same result faster

Detailed Misconception: "Mark Visited When Processing"

This is a subtle but important error:

Incorrect:

while queue:
    current = queue.popleft()
    visited.add(current)  # WRONG: too late!
    for neighbor in graph[current]:
        if neighbor not in visited:
            queue.append(neighbor)

Problem: A vertex might be added to the queue multiple times before being processed, wasting time and potentially causing issues.

Correct:

while queue:
    current = queue.popleft()
    for neighbor in graph[current]:
        if neighbor not in visited:
            visited.add(neighbor)  # RIGHT: mark immediately
            queue.append(neighbor)

Key Insight: Mark visited at discovery time (when adding to queue), not processing time (when dequeuing). This ensures each vertex is added exactly once.

When to Use (and Not Use) BFS

Armed with deep understanding of why BFS works, you can make informed decisions about algorithm selection.

Algorithm Selection Guide
Scenario	Algorithm	Why
Unweighted graph, shortest path	BFS	O(V+E), simple, correct
All edges weight 1	BFS	Same as unweighted
All edges same positive weight	BFS	Minimizing hops = minimizing cost
Variable non-negative weights	Dijkstra's	Need priority queue for correct ordering
Negative weights (no negative cycles)	Bellman-Ford	Dijkstra's fails with negative weights
All-pairs shortest paths	Floyd-Warshall or repeated Dijkstra's	Depends on graph density
Edge weights 0 or 1 only	0-1 BFS	O(V+E) with deque trick
Just need any path (not shortest)	BFS or DFS	Both work; DFS may be simpler
Need shortest path AND minimum cost	Check if weights equal	If equal: BFS. Otherwise: Dijkstra's

The Decision Process

Summary: Why BFS Works

Let's consolidate the deep understanding we've developed:

Key Takeaways

•FIFO queue preserves level order — Vertices at distance k are all processed before any at distance k+1
•First discovery is optimal — The queue ordering means the first path to any vertex is the shortest
•Inductive proof of correctness — Strong induction on distance proves BFS assigns correct distances
•Unit weight condition — BFS works when all edges have equal cost (not just weight 1)
•Fails for variable weights — Different edge costs break the "first discovery = optimal" property
•BFS is simplified Dijkstra's — With equal weights, priority queue degrades to FIFO queue
•Loop invariants guarantee correctness — Formal verification via invariant maintenance
•Algorithm selection — Match algorithm to weight structure: BFS, Dijkstra's, Bellman-Ford, etc.

Module Complete:

You now have a complete, rigorous understanding of shortest paths in unweighted graphs using BFS:

Why BFS finds shortest paths — The level-order property and optimality theorem
Parent tracking — Reconstructing the actual path, not just its length
Distance array — Efficient distance queries and multi-source BFS
Deep theoretical foundation — Invariants, proofs, and algorithm selection

Module Complete