Shortest Path in Unweighted Graph Using BFS in DSA Rust

Mental Model

We find the shortest path by exploring neighbors level by level, like ripples spreading in water.

Analogy: Imagine you are in a maze and shout to find the shortest way out. Your shout reaches nearby friends first, then their friends, spreading out evenly until someone finds the exit.

Graph:
0 -> 1 -> 2
↓    ↓
3    4

Start at node 0, explore neighbors 1 and 3 first, then neighbors of 1 and 3, and so on.

Dry Run Walkthrough

Input: Graph edges: 0-1, 0-3, 1-2, 1-4; Find shortest path from 0 to 4

Goal: Find the shortest path from node 0 to node 4 using BFS

Step 1: Start BFS from node 0, mark distance 0

Queue: [0]
Distances: 0=0, others=∞

Why: We begin from the start node with distance zero

Step 2: Dequeue 0, enqueue neighbors 1 and 3 with distance 1

Queue: [1, 3]
Distances: 0=0, 1=1, 3=1, others=∞

Why: Neighbors of 0 are one step away

Step 3: Dequeue 1, enqueue neighbors 2 and 4 with distance 2

Queue: [3, 2, 4]
Distances: 0=0, 1=1, 3=1, 2=2, 4=2

Why: Neighbors of 1 are two steps away from start

Step 4: Dequeue 3, no new neighbors to enqueue

Queue: [2, 4]
Distances unchanged

Why: 3 has no unvisited neighbors

Step 5: Dequeue 2, no new neighbors to enqueue

Queue: [4]
Distances unchanged

Why: 2 has no unvisited neighbors

Step 6: Dequeue 4, target found with distance 2

Queue: []
Distances unchanged

Why: Reached target node 4 with shortest distance

Result:

Shortest path distance from 0 to 4 is 2

Annotated Code

DSA Rust

use std::collections::{VecDeque, HashMap};

fn shortest_path_bfs(graph: &HashMap<usize, Vec<usize>>, start: usize, target: usize) -> Option<usize> {
    let mut queue = VecDeque::new();
    let mut distances = HashMap::new();
    queue.push_back(start);
    distances.insert(start, 0);

    while let Some(node) = queue.pop_front() {
        if node == target {
            return distances.get(&node).copied();
        }
        if let Some(neighbors) = graph.get(&node) {
            for &neighbor in neighbors {
                if !distances.contains_key(&neighbor) {
                    distances.insert(neighbor, distances[&node] + 1);
                    queue.push_back(neighbor);
                }
            }
        }
    }
    None
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(0, vec![1, 3]);
    graph.insert(1, vec![2, 4]);
    graph.insert(2, vec![]);
    graph.insert(3, vec![]);
    graph.insert(4, vec![]);

    let start = 0;
    let target = 4;
    match shortest_path_bfs(&graph, start, target) {
        Some(distance) => println!("Shortest path distance from {} to {} is {}", start, target, distance),
        None => println!("No path found from {} to {}", start, target),
    }
}

queue.push_back(start); distances.insert(start, 0);

Initialize BFS queue and set start node distance to zero

while let Some(node) = queue.pop_front() {

Process nodes in FIFO order to explore neighbors level by level

if node == target { return distances.get(&node).copied(); }

Stop search when target node is found and return its distance

for &neighbor in neighbors { if !distances.contains_key(&neighbor) { distances.insert(neighbor, distances[&node] + 1); queue.push_back(neighbor); } }

Add unvisited neighbors to queue with distance one more than current node

Output

Shortest path distance from 0 to 4 is 2

Complexity Analysis

Time: O(V + E) because BFS visits every vertex and edge once

Space: O(V) for storing distances and queue for vertices

vs Alternative: Compared to DFS, BFS guarantees shortest path in unweighted graphs by exploring level by level

Edge Cases

Start node equals target node

Returns distance 0 immediately

DSA Rust

if node == target { return distances.get(&node).copied(); }

No path exists between start and target

Returns None after exploring all reachable nodes

DSA Rust

None

Graph with isolated nodes

Only reachable nodes are visited; unreachable nodes ignored

DSA Rust

if let Some(neighbors) = graph.get(&node)

When to Use This Pattern

When asked for shortest path in an unweighted graph, use BFS because it explores nodes in order of distance from start.

Common Mistakes

Mistake: Using DFS which does not guarantee shortest path in unweighted graphs
Fix: Use BFS to explore neighbors level by level for shortest path

Mistake: Not marking visited nodes, causing infinite loops
Fix: Track visited nodes using a distances map or set before enqueueing

Summary

Finds shortest path distance in unweighted graphs using BFS traversal.

Use when you need the minimum number of edges between two nodes in an unweighted graph.

BFS explores neighbors level by level, ensuring the first time you reach a node is via the shortest path.

Practice

1. What does BFS (Breadth-First Search) find in an unweighted graph when used from a start node?

easy

A. A random path to any node

B. The longest path in the graph

C. The path with the maximum sum of edge weights

D. The shortest path in terms of number of edges to all reachable nodes

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level, starting from the source node, visiting all neighbors before moving deeper.

2. Step 2: BFS finds shortest paths in unweighted graphs

   Because BFS visits nodes in order of increasing distance (edges), it finds the shortest path in terms of edge count.

3. Final Answer:

   The shortest path in terms of number of edges to all reachable nodes -> Option D

4. Quick Check:

   BFS = shortest path in unweighted graph [OK]

Hint: BFS finds shortest paths by layers in unweighted graphs [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds longest paths
• Assuming BFS works for weighted graphs without modification

2. Which Rust code snippet correctly initializes a queue for BFS traversal?

easy

A. let queue = Vec::new();

B. let mut queue = std::collections::VecDeque::new();

C. let mut queue = std::collections::HashMap::new();

D. let mut queue = std::collections::BinaryHeap::new();

Solution

1. Step 1: Identify the correct queue type for BFS

   BFS requires a FIFO queue; VecDeque in Rust supports efficient push/pop from both ends.

2. Step 2: Check each option's suitability

   let mut queue = std::collections::VecDeque::new(); uses VecDeque which is correct; Vec (A) is not efficient as a queue; HashMap (C) is a map, not a queue; BinaryHeap (D) is a priority queue, not FIFO.

3. Final Answer:

   let mut queue = std::collections::VecDeque::new(); -> Option B

4. Quick Check:

   VecDeque = correct BFS queue [OK]

Hint: Use VecDeque for BFS queue in Rust [OK]

Common Mistakes:

• Using Vec instead of VecDeque for queue
• Using HashMap or BinaryHeap incorrectly
• Not mutably declaring the queue

3. Given the following Rust code snippet for BFS on an unweighted graph, what is the output distance vector?

let graph = vec![
    vec![1, 2],
    vec![0, 3],
    vec![0, 3],
    vec![1, 2, 4],
    vec![3]
];
let start = 0;
let mut dist = vec![-1; 5];
dist[start] = 0;
let mut queue = std::collections::VecDeque::new();
queue.push_back(start);

while let Some(u) = queue.pop_front() {
    for &v in &graph[u] {
        if dist[v] == -1 {
            dist[v] = dist[u] + 1;
            queue.push_back(v);
        }
    }
}
println!("{:?}", dist);

medium

A. 0, 1, 1, 2, 3

B. 0, 1, 2, 1, 2

C. 0, 1, 1, 1, 2

D. 0, 2, 2, 3, 4

Solution

1. Step 1: Trace BFS distances from start node 0

   Start at node 0 (distance 0). Neighbors 1 and 2 get distance 1. Then from 1 and 2, node 3 gets distance 2. From 3, node 4 gets distance 3.

2. Step 2: Confirm final distance vector

   Distances: node0=0, node1=1, node2=1, node3=2, node4=3.

3. Final Answer:

   0, 1, 1, 2, 3 -> Option A

4. Quick Check:

   BFS distances = [0,1,1,2,3] [OK]

Hint: Track BFS levels to assign distances [OK]

Common Mistakes:

• Mixing up node indices and distances
• Assigning wrong distances to nodes visited later
• Forgetting to initialize distances with -1

4. Identify the bug in this BFS Rust code snippet that causes it to panic or produce incorrect distances:

let graph = vec![vec![1], vec![0, 2], vec![1]];
let start = 0;
let mut dist = vec![0; 3];
let mut queue = std::collections::VecDeque::new();
queue.push_back(start);

while let Some(u) = queue.pop_front() {
    for &v in &graph[u] {
        if dist[v] == 0 {
            dist[v] = dist[u] + 1;
            queue.push_back(v);
        }
    }
}
println!("{:?}", dist);

medium

A. Loop condition is incorrect

B. Queue is not mutable

C. Distance vector initialized with zeros causes confusion with unvisited nodes

D. Graph adjacency list is empty

Solution

1. Step 1: Check distance vector initialization

   Distances initialized to 0 means unvisited nodes and start node share same value, causing logic errors.

2. Step 2: Explain impact on BFS logic

   Condition 'if dist[v] == 0' fails to distinguish unvisited nodes, so some nodes never get updated or cause infinite loops.

3. Final Answer:

   Distance vector initialized with zeros causes confusion with unvisited nodes -> Option C

4. Quick Check:

   Use -1 for unvisited distances [OK]

Hint: Initialize distances with -1 to mark unvisited [OK]

Common Mistakes:

• Using 0 as initial distance for all nodes
• Not marking start node distance before BFS
• Ignoring mutability of queue

5. You want to find the shortest path length from node 0 to node 5 in this unweighted graph using BFS. The graph edges are:

0 - 1, 0 - 2, 1 - 3, 2 - 3, 3 - 4, 4 - 5

Which BFS distance array after traversal correctly shows the shortest distance to each node from 0? Assume nodes are 0 to 5 and unreachable nodes have distance -1.

hard

A. [0, 1, 1, 2, 3, 4]

B. [0, 1, 2, 3, 4, 5]

C. [0, 1, 1, 1, 2, 3]

D. [0, -1, -1, -1, -1, -1]

Solution

1. Step 1: Map shortest paths from node 0

   From 0: nodes 1 and 2 are 1 edge away; node 3 is 2 edges away (via 1 or 2); node 4 is 3 edges away; node 5 is 4 edges away.

2. Step 2: Confirm distances array

   Distances: 0=0, 1=1, 2=1, 3=2, 4=3, 5=4 matches [0, 1, 1, 2, 3, 4].

3. Final Answer:

   [0, 1, 1, 2, 3, 4] -> Option A

4. Quick Check:

   Shortest path distances = [0,1,1,2,3,4] [OK]

Hint: Count edges from start node to each node [OK]

Common Mistakes:

• Counting nodes instead of edges
• Mislabeling unreachable nodes
• Confusing path length with node values