Shortest Path in Unweighted Graph Using BFS in DSA C++

Mental Model

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

Analogy: Imagine you are in a city with streets connecting intersections. To find the shortest way to a friend's house, you check all intersections one step away first, then two steps away, and so on until you find your friend.

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

Start at 0, explore neighbors 1 and 3 first, then neighbors of 1 and 3, etc.

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] = 0

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

Why: We begin from the start node with distance zero

Step 2: Dequeue 0, enqueue neighbors 1 and 3, set distance[1] = 1, distance[3] = 1

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

Why: Neighbors of 0 are one step away

Step 3: Dequeue 1, enqueue neighbors 2 and 4, set distance[2] = 2, distance[4] = 2

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

Why: Neighbors of 1 are two steps away from start

Step 4: Dequeue 3, no new neighbors to enqueue

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

Why: 3 has no unvisited neighbors

Step 5: Dequeue 2, no new neighbors to enqueue

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

Why: 2 has no unvisited neighbors

Step 6: Dequeue 4, target found with distance 2

Queue: []
Distances: [0, 1, 2, 1, 2]

Why: Reached target node 4 with shortest distance

Result:

Shortest distance from 0 to 4 is 2

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

class Graph {
public:
    int V;
    vector<vector<int>> adj;

    Graph(int vertices) {
        V = vertices;
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // undirected graph
    }

    int shortestPathBFS(int start, int target) {
        vector<int> distance(V, INT_MAX);
        queue<int> q;

        distance[start] = 0; // start node distance is zero
        q.push(start);

        while (!q.empty()) {
            int curr = q.front();
            q.pop();

            if (curr == target) {
                return distance[curr]; // found shortest path
            }

            for (int neighbor : adj[curr]) {
                if (distance[neighbor] == INT_MAX) {
                    distance[neighbor] = distance[curr] + 1; // update distance
                    q.push(neighbor); // enqueue neighbor
                }
            }
        }
        return -1; // target not reachable
    }
};

int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 3);
    g.addEdge(1, 2);
    g.addEdge(1, 4);

    int start = 0;
    int target = 4;
    int dist = g.shortestPathBFS(start, target);

    if (dist != -1) {
        cout << "Shortest distance from " << start << " to " << target << " is " << dist << "\n";
    } else {
        cout << "Target not reachable from start\n";
    }
    return 0;
}

distance[start] = 0; // start node distance is zero

Initialize start node distance to zero

q.push(start);

Begin BFS by enqueueing start node

int curr = q.front(); q.pop();

Dequeue current node to explore neighbors

if (curr == target) { return distance[curr]; }

If target found, return shortest distance immediately

for (int neighbor : adj[curr]) { if (distance[neighbor] == INT_MAX) { distance[neighbor] = distance[curr] + 1; q.push(neighbor); } }

For each unvisited neighbor, update distance and enqueue

Output

Shortest distance from 0 to 4 is 2

Complexity Analysis

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

Space: O(V) for distance array and queue storing vertices

vs Alternative: Compared to DFS which may explore longer paths first, BFS guarantees shortest path in unweighted graphs efficiently

Edge Cases

Start node equals target node

Distance is zero immediately returned

DSA C++

if (curr == target) { return distance[curr]; }

Target node not reachable from start

Returns -1 indicating no path

DSA C++

return -1; // target not reachable

Graph with isolated nodes

Distances remain INT_MAX for unreachable nodes, BFS skips them

DSA C++

if (distance[neighbor] == INT_MAX)

When to Use This Pattern

When asked for shortest path in an unweighted graph, use BFS because it explores nodes in order of distance, ensuring the first time you reach the target is the shortest path.

Common Mistakes

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

Mistake: Not marking visited nodes or distances, causing infinite loops or revisits
Fix: Track visited nodes or distances to avoid revisiting

Summary

Finds shortest path distance in an unweighted graph using BFS traversal.

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

BFS explores nodes in layers, so the first time you reach the target is the shortest path.

Practice

1. What is the main purpose of using BFS (Breadth-First Search) in an unweighted graph?

easy

A. To sort the nodes in topological order

B. To find the maximum depth of the graph

C. To find the shortest path from a source node to all other nodes

D. To detect cycles in the graph

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level starting from the source node.

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

   Because BFS visits nodes in order of increasing distance, it finds shortest paths from source to all nodes.

3. Final Answer:

   To find the shortest path from a source node to all other nodes -> Option C

4. Quick Check:

   BFS shortest path = D [OK]

Hint: BFS explores neighbors level-wise to find shortest paths [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds maximum depth
• Assuming BFS sorts nodes topologically

2. Which of the following is the correct way to initialize a queue for BFS in C++?

easy

A. queue<int> q; q.push(0);

B. stack<int> q; q.push(0);

C. queue<int> q; q.insert(0);

D. queue<int> q; q.add(0);

Solution

1. Step 1: Identify correct queue declaration

   In C++, BFS uses std::queue with push() to add elements.

2. Step 2: Check method names

   push() is correct for queue; insert() and add() are invalid; stack is wrong data structure.

3. Final Answer:

   queue<int> q; q.push(0); -> Option A

4. Quick Check:

   queue push() method = C [OK]

Hint: Use std::queue and push() to add elements in BFS [OK]

Common Mistakes:

• Using stack instead of queue
• Using insert() or add() instead of push()
• Confusing queue methods with vector methods

3. Consider the following C++ code snippet for BFS shortest path in an unweighted graph:

int n = 4;
vector adj = {{1,2}, {0,2,3}, {0,1,3}, {1,2}};
vector<int> dist(n, -1);
queue<int> q;
dist[0] = 0;
q.push(0);
while(!q.empty()) {
  int u = q.front(); q.pop();
  for(int v : adj[u]) {
    if(dist[v] == -1) {
      dist[v] = dist[u] + 1;
      q.push(v);
    }
  }
}
for(int i=0; iWhat is the output?

medium

A. 0 1 1 2

B. 0 1 2 3

C. 0 2 1 1

D. 0 1 1 1

Solution

1. Step 1: Initialize distances and start BFS

   dist[0]=0, others -1; start from node 0.

2. Step 2: BFS visits neighbors and updates distances

   From 0: neighbors 1,2 get dist=1; from 1 and 2: neighbor 3 gets dist=2.

3. Final Answer:

   0 1 1 2 -> Option A

4. Quick Check:

   BFS distance array = 0 1 1 2 [OK]

Hint: BFS distance increments by 1 per level from source [OK]

Common Mistakes:

• Mixing up node indices and distances
• Not initializing distances to -1
• Forgetting to check if node was visited

4. The following BFS code snippet is intended to find shortest paths in an unweighted graph. Identify the bug:

int n = 3;
vector adj = {{1}, {0,2}, {1}};
vector<int> dist(n, 0);
queue<int> q;
dist[0] = 0;
q.push(0);
while(!q.empty()) {
  int u = q.front(); q.pop();
  for(int v : adj[u]) {
    if(dist[v] == 0) {
      dist[v] = dist[u] + 1;
      q.push(v);
    }
  }
}
for(int i=0; i

medium

A. dist[u] is not updated inside the loop

B. Queue is not used properly

C. Adjacency list is incorrect

D. dist vector initialized with 0 instead of -1

Solution

1. Step 1: Check distance initialization

   dist initialized with 0 means unvisited nodes are indistinguishable from source.

2. Step 2: Identify impact on BFS logic

   Condition dist[v] == 0 fails to detect unvisited nodes correctly, causing wrong or no updates.

3. Final Answer:

   dist vector initialized with 0 instead of -1 -> Option D

4. Quick Check:

   dist init must be -1 to mark unvisited [OK]

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

Common Mistakes:

• Using 0 as unvisited marker
• Not checking visited condition properly
• Misusing queue operations

5. You have an unweighted graph with 5 nodes and edges: 0-1, 0-2, 1-3, 2-3, 3-4. Using BFS from node 0, what is the shortest path distance to node 4? Also, which nodes are on one shortest path from 0 to 4?

hard

A. Distance: 2; Path: 0 -> 1 -> 3 -> 4

B. Distance: 3; Path: 0 -> 2 -> 3 -> 4

C. Distance: 2; Path: 0 -> 3 -> 4

D. Distance: 4; Path: 0 -> 2 -> 3 -> 4

Solution

1. Step 1: Build graph and run BFS from node 0

   Edges: 0-1,0-2; 1-3; 2-3; 3-4. BFS levels: 0(dist=0), 1 and 2(dist=1), 3(dist=2), 4(dist=3).

2. Step 2: Identify shortest path to node 4

   Shortest distance to 4 is 3. Paths: 0->1->3->4 or 0->2->3->4. Distance: 3; Path: 0 -> 2 -> 3 -> 4 shows correct distance and one valid path.

3. Final Answer:

   Distance: 3; Path: 0 -> 2 -> 3 -> 4 -> Option B

4. Quick Check:

   Shortest path length = 3 via node 2 [OK]

Hint: Trace BFS levels to find shortest path and distance [OK]

Common Mistakes:

• Assuming direct edge from 0 to 3
• Confusing distance with number of edges
• Ignoring multiple shortest paths