Shortest Path in Unweighted Graph Using BFS in DSA C++ - Deep Dive

Overview - Shortest Path in Unweighted Graph Using BFS

What is it?

The shortest path in an unweighted graph is the path with the fewest edges between two points. Breadth-First Search (BFS) is a method to explore all nodes layer by layer, starting from a source node. Using BFS, we can find the shortest path in terms of edges because it visits nodes in order of their distance from the source. This approach works only when all edges have the same weight or no weight at all.

Why it matters

Without a way to find the shortest path efficiently, many real-world problems like navigation, network routing, and social connections would be slow or impossible to solve quickly. BFS provides a simple and fast way to find the shortest path in unweighted graphs, making systems responsive and reliable. Without it, applications would waste time exploring longer or irrelevant paths, causing delays and inefficiencies.

Where it fits

Before learning this, you should understand basic graph concepts like nodes, edges, and adjacency lists or matrices. You should also know how BFS works for simple graph traversal. After mastering shortest path with BFS, you can learn shortest paths in weighted graphs using algorithms like Dijkstra's or Bellman-Ford.

Mental Model

Core Idea

BFS explores nodes in layers from the start, so the first time it reaches a node, it has found the shortest path to it.

Think of it like...

Imagine standing in a room and calling out to friends in other rooms. The friends closest to you hear you first, then their neighbors, and so on. The order in which they hear you shows the shortest number of doors between you and them.

Start (S)
  │
  ├─ Level 1 nodes (neighbors of S)
  │    │
  │    ├─ Level 2 nodes (neighbors of Level 1)
  │    │    │
  │    │    └─ ... and so on

BFS visits nodes level by level, ensuring shortest paths.

Build-Up - 7 Steps

1

Foundation

Understanding Graph Representation

Concept: Graphs can be represented using adjacency lists or matrices to store connections between nodes.

A graph consists of nodes (vertices) and edges (connections). For example, an adjacency list stores for each node a list of its neighbors. This structure allows quick access to connected nodes, which BFS uses to explore the graph.

Result

You can store and access graph connections efficiently, enabling traversal algorithms like BFS.

Knowing how graphs are stored is essential because BFS depends on quickly finding neighbors to explore next.

2

Foundation

Basics of Breadth-First Search

Concept: BFS explores nodes in order of their distance from the start node using a queue.

BFS starts at a source node, marks it visited, and adds it to a queue. Then it repeatedly removes the front node from the queue, visits its neighbors, marks them visited, and adds them to the queue. This process continues until all reachable nodes are visited.

Result

Nodes are visited in layers, with closer nodes visited before farther ones.

Understanding BFS traversal order is key to using it for shortest path because it naturally finds the shortest distance in unweighted graphs.

3

Intermediate

Tracking Distance During BFS

🤔Before reading on: Do you think BFS needs extra storage to remember how far each node is from the start? Commit to yes or no.

Concept: To find shortest paths, BFS keeps track of the distance from the start node to each visited node.

Along with marking nodes visited, BFS stores a distance array initialized with -1 (meaning unvisited). The start node distance is 0. When BFS visits a neighbor for the first time, it sets its distance to the current node's distance plus one.

Result

After BFS finishes, the distance array holds the shortest number of edges from the start to every node.

Tracking distance during BFS leverages its layer-by-layer nature to directly measure shortest paths without extra searching.

4

Intermediate

Reconstructing the Shortest Path

🤔Before reading on: Can BFS alone tell you the exact nodes on the shortest path, or just the distance? Commit to your answer.

Concept: To find the actual shortest path, BFS stores the parent of each node when it is first visited.

Alongside distance, BFS keeps a parent array where parent[node] is the node from which it was discovered. After BFS, starting from the target node, you can follow parents backward to the start node, reversing this sequence to get the shortest path.

Result

You can output the exact sequence of nodes forming the shortest path from start to target.

Knowing how to reconstruct paths turns BFS from a distance finder into a full path finder, which is often needed in real applications.

5

Intermediate

Implementing BFS for Shortest Path in C++

🤔Before reading on: Do you think BFS code for shortest path is much more complex than simple BFS traversal? Commit to yes or no.

Concept: BFS code for shortest path adds distance and parent tracking but remains simple and efficient.

Here is a complete C++ example: #include #include #include #include using namespace std; void bfs_shortest_path(const vector>& graph, int start, int target) { int n = graph.size(); vector distance(n, -1); vector parent(n, -1); queue q; distance[start] = 0; q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); if (node == target) break; for (int neighbor : graph[node]) { if (distance[neighbor] == -1) { distance[neighbor] = distance[node] + 1; parent[neighbor] = node; q.push(neighbor); } } } if (distance[target] == -1) { cout << "No path found" << endl; return; } vector path; for (int cur = target; cur != -1; cur = parent[cur]) { path.push_back(cur); } reverse(path.begin(), path.end()); cout << "Shortest path length: " << distance[target] << "\nPath: "; for (int node : path) { cout << node << " "; } cout << endl; } int main() { vector> graph = { {1, 2}, // neighbors of node 0 {0, 3}, // neighbors of node 1 {0, 3}, // neighbors of node 2 {1, 2, 4}, // neighbors of node 3 {3} // neighbors of node 4 }; bfs_shortest_path(graph, 0, 4); return 0; }

Result

Output: Shortest path length: 3 Path: 0 1 3 4

Seeing the full code shows BFS for shortest path is straightforward and practical, reinforcing that BFS is a powerful tool for unweighted graphs.

6

Advanced

Handling Multiple Shortest Paths

🤔Before reading on: Does BFS find all shortest paths or just one? Commit to your answer.

Concept: BFS finds one shortest path, but with modifications, it can count or list all shortest paths.

By tracking the number of ways to reach each node at the shortest distance, BFS can count how many shortest paths exist. This requires an additional array to accumulate counts when a node is reached with the same shortest distance again.

Result

You can know not only the shortest distance but also how many shortest paths connect two nodes.

Understanding BFS extensions for multiple shortest paths reveals its flexibility and deeper graph insights beyond just one path.

7

Expert

Optimizations and Limitations of BFS Shortest Path

🤔Before reading on: Is BFS always the best choice for shortest path in all graphs? Commit to yes or no.

Concept: BFS is optimal for unweighted graphs but has limits and can be optimized for large or special graphs.

BFS uses O(V+E) time and memory, which can be large for huge graphs. Optimizations include early stopping when target is found, bidirectional BFS (searching from start and target simultaneously), and using adjacency structures that reduce overhead. BFS cannot handle weighted edges; for those, algorithms like Dijkstra's are needed.

Result

You learn when BFS is efficient and when to switch to other methods or optimizations.

Knowing BFS's boundaries and improvements prepares you for real-world challenges and advanced graph algorithms.

Under the Hood

BFS uses a queue to explore nodes in order of their distance from the start. When a node is dequeued, all its unvisited neighbors are enqueued and marked with a distance one greater than the current node. This ensures that the first time a node is visited, the shortest path to it is found. The parent array records the path by remembering which node led to each neighbor.

Why designed this way?

BFS was designed to explore graphs level by level to guarantee shortest paths in unweighted graphs. Using a queue ensures nodes are processed in the order they are discovered, preventing revisiting nodes unnecessarily. Alternatives like Depth-First Search do not guarantee shortest paths because they explore deeply before exploring neighbors.

┌─────────────┐
│ Start Node  │
└─────┬───────┘
      │
      ▼
┌─────────────┐      ┌─────────────┐
│ Queue Front │─────▶│ Visit Neigh │
└─────────────┘      └─────┬───────┘
                             │
                             ▼
                    ┌─────────────────┐
                    │ Mark Distance &  │
                    │ Parent, Enqueue  │
                    └────────┬────────┘
                             │
                             ▼
                      Repeat until
                      queue empty or
                      target found

Myth Busters - 3 Common Misconceptions

Quick: Does BFS find shortest paths in weighted graphs? Commit to yes or no.

Common Belief: BFS always finds the shortest path regardless of edge weights.

Reality: BFS only finds shortest paths in unweighted graphs or graphs where all edges have equal weight.

Why it matters: Using BFS on weighted graphs can give incorrect paths, leading to wrong decisions in routing or navigation.

Quick: Does BFS always find the shortest path faster than other algorithms? Commit to yes or no.

Common Belief: BFS is always the fastest way to find shortest paths in any graph.

Reality: BFS is efficient for unweighted graphs but not suitable for weighted graphs or very large sparse graphs where other algorithms or heuristics perform better.

Why it matters: Choosing BFS blindly can cause performance issues or incorrect results in complex graphs.

Quick: Does BFS store the full path automatically without extra work? Commit to yes or no.

Common Belief: BFS traversal alone gives the full shortest path from start to target.

Reality: BFS traversal gives the order of visiting nodes and distances but requires storing parent information to reconstruct the actual path.

Why it matters: Without parent tracking, you only know the distance, not the route, which limits practical use.

Expert Zone

1

Bidirectional BFS can halve search time by simultaneously searching from start and target, meeting in the middle.

2

In very large graphs, using adjacency lists with efficient memory layouts improves cache performance and speeds up BFS.

3

When multiple shortest paths exist, BFS can be extended to count or list them by careful bookkeeping, which is useful in probabilistic or network reliability analyses.

When NOT to use

Do not use BFS for graphs with weighted edges; instead, use Dijkstra's or Bellman-Ford algorithms. For extremely large graphs where memory is limited, consider heuristic or approximate methods like A* or landmark-based searches.

Production Patterns

In real systems, BFS is used for social network friend suggestions, shortest path in unweighted road maps, and network broadcast simulations. Bidirectional BFS is common in routing engines to reduce latency. BFS combined with parent tracking is used in puzzle solvers and AI pathfinding where all moves cost the same.

Connections

Dijkstra's Algorithm

Builds on BFS by handling weighted edges with a priority queue.

Understanding BFS as a special case of Dijkstra's algorithm with equal weights helps grasp shortest path algorithms as a family.

Queue Data Structure

BFS relies on queues to explore nodes in order of discovery.

Knowing how queues work clarifies why BFS visits nodes layer by layer, ensuring shortest paths.

Wave Propagation in Physics

BFS exploration mimics waves spreading out evenly from a source point.

Recognizing BFS as a wave-like process helps understand its layer-by-layer nature and why it finds shortest paths first.

Common Pitfalls

#1 Not marking nodes visited immediately when enqueued, causing repeated visits.

Wrong approach:

for (int neighbor : graph[node]) {
if (distance[neighbor] == -1) {
q.push(neighbor);
distance[neighbor] = distance[node] + 1;
}
}
// Marking visited after dequeueing neighbors

Correct approach:

for (int neighbor : graph[node]) {
if (distance[neighbor] == -1) {
distance[neighbor] = distance[node] + 1;
q.push(neighbor);
}
}

Root cause:

Delaying marking visited allows the same node to be enqueued multiple times, causing inefficiency and incorrect distances.

#2 Using BFS on weighted graphs expecting correct shortest paths.

Wrong approach:

Run BFS on a graph where edges have different weights and trust the distance array as shortest path lengths.

Correct approach:

Use Dijkstra's algorithm or Bellman-Ford for weighted graphs to find correct shortest paths.

Root cause:

BFS assumes equal edge cost; ignoring weights leads to wrong path lengths.

#3 Not reconstructing the path using parent array, only printing distance.

Wrong approach:

cout << "Shortest distance: " << distance[target] << endl; // No path output

Correct approach:

Use parent array to backtrack from target to start and print the full path.

Root cause:

Confusing distance with path; distance alone does not show the route taken.

Key Takeaways

BFS explores nodes in layers, guaranteeing the shortest path in unweighted graphs by visiting closer nodes first.

Tracking distance and parent information during BFS allows you to find both the length and the exact nodes of the shortest path.

BFS is simple, efficient, and perfect for unweighted graphs but cannot handle weighted edges correctly.

Optimizations like bidirectional BFS and careful data structures improve BFS performance in large graphs.

Understanding BFS's limitations and extensions prepares you for more advanced shortest path algorithms and real-world applications.

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