Why Shortest Path in Unweighted Graph Using BFS in DSA Rust?

The Big Idea

What if you could find the shortest path in a maze without trying every turn?

The Scenario

Imagine you are in a city with many streets and intersections. You want to find the shortest way to walk from your home to a friend's house without knowing the map well.

If you try to guess paths one by one, it can take a very long time and you might get lost.

The Problem

Trying every possible path manually is slow and confusing. You might walk in circles or take longer routes without realizing it.

It is easy to make mistakes and waste time, especially when the city is big and has many streets.

The Solution

Using a method called Breadth-First Search (BFS), you explore all nearby intersections first, then move further step by step.

This way, you find the shortest path quickly and without missing any shorter routes.

Before vs After

✗ Before

fn find_path(graph: &Vec<Vec<usize>>, start: usize, end: usize) {
    // Try all paths manually (very complex and slow)
}

✓ After

fn shortest_path_bfs(graph: &Vec<Vec<usize>>, start: usize, end: usize) -> Option<Vec<usize>> {
    // Use BFS to find shortest path efficiently
}

What It Enables

This lets you quickly find the shortest route in any network without guessing or wasting time.

Real Life Example

GPS apps use this idea to show you the fastest way to drive or walk in a city with many roads.

Key Takeaways

Manual path search is slow and error-prone.

BFS explores neighbors level by level to find shortest paths.

This method is efficient and reliable for unweighted graphs.

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