Shortest Path in Unweighted Graph Using BFS in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS shortest path distance array

What is the output of the distance array after running BFS from node 0 in the given graph?

DSA Javascript

const graph = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 3],
  3: [1, 2, 4],
  4: [3]
};

function bfsShortestPath(graph, start) {
  const queue = [start];
  const distances = {};
  for (const node in graph) {
    distances[node] = -1;
  }
  distances[start] = 0;

  while (queue.length > 0) {
    const current = queue.shift();
    for (const neighbor of graph[current]) {
      if (distances[neighbor] === -1) {
        distances[neighbor] = distances[current] + 1;
        queue.push(neighbor);
      }
    }
  }
  return distances;
}

console.log(bfsShortestPath(graph, 0));

A {"0":0,"1":1,"2":2,"3":2,"4":3}

B {"0":0,"1":1,"2":1,"3":1,"4":2}

C {"0":0,"1":-1,"2":1,"3":2,"4":3}

D {"0":0,"1":1,"2":1,"3":2,"4":3}

💡 Hint

Think about how BFS explores neighbors level by level starting from the start node.

BFS starts at node 0 with distance 0. Nodes 1 and 2 are directly connected to 0, so distance 1. Node 3 is connected to 1 and 2, so distance 2. Node 4 is connected to 3, so distance 3.

🧠 Conceptual

intermediate

Why BFS finds shortest path in unweighted graphs?

Why does BFS guarantee the shortest path in an unweighted graph?

A Because BFS uses a stack to explore nodes deeply before backtracking.

B Because BFS explores nodes in order of their distance from the start node, layer by layer.

C Because BFS assigns random distances and picks the smallest at the end.

D Because BFS only visits nodes with the highest degree first.

💡 Hint

Think about how BFS visits nodes closest to the start before farther ones.

BFS explores all nodes at distance k before nodes at distance k+1, ensuring the first time a node is visited is via the shortest path.

🔧 Debug

advanced

Identify the error in BFS shortest path code

What error will this BFS code produce when run on the graph below?

DSA Javascript

const graph = {
  0: [1],
  1: [0, 2],
  2: [1]
};

function bfsShortestPath(graph, start) {
  const queue = [start];
  const distances = {};
  for (const node in graph) {
    distances[node] = 0;
  }
  distances[start] = 0;

  while (queue.length > 0) {
    const current = queue.shift();
    for (const neighbor of graph[current]) {
      if (distances[neighbor] === 0) {
        distances[neighbor] = distances[current] + 1;
        queue.push(neighbor);
      }
    }
  }
  return distances;
}

console.log(bfsShortestPath(graph, 0));

A The code runs but returns incorrect distances because unvisited nodes are initialized to 0.

B SyntaxError due to missing semicolon after queue initialization.

C The code runs correctly and returns the right distances.

D TypeError because graph[current] is undefined.

💡 Hint

Check how unvisited nodes are marked and how the condition to visit neighbors is checked.

Initializing all distances to 0 causes confusion between visited and unvisited nodes. Nodes with distance 0 are treated as visited, so some nodes are never visited, leading to wrong results.

❓ Predict Output

advanced

Output of BFS path reconstruction

What is the output path from node 0 to node 4 after running BFS and reconstructing the path?

DSA Javascript

const graph = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 3],
  3: [1, 2, 4],
  4: [3]
};

function bfsPath(graph, start, end) {
  const queue = [start];
  const visited = new Set([start]);
  const parent = {};

  while (queue.length > 0) {
    const current = queue.shift();
    if (current === end) break;
    for (const neighbor of graph[current]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        parent[neighbor] = current;
        queue.push(neighbor);
      }
    }
  }

  const path = [];
  let node = end;
  while (node !== undefined) {
    path.push(node);
    node = parent[node];
  }
  return path.reverse();
}

console.log(bfsPath(graph, 0, 4));

A [0, 1, 3, 4]

B [0, 2, 3, 4]

C [0, 3, 4]

D [4, 3, 1, 0]

💡 Hint

Check which neighbor is visited first in BFS and how parent links are set.

BFS visits node 1 before node 2 from node 0, so the path to 4 is 0 -> 1 -> 3 -> 4.

🧠 Conceptual

expert

Why BFS is not suitable for weighted graphs

Why is BFS not suitable for finding shortest paths in weighted graphs with different edge weights?

A Because BFS uses recursion which is inefficient for weighted graphs.

B Because BFS only works on directed graphs, not weighted graphs.

C Because BFS treats all edges as equal cost and cannot handle varying weights correctly.

D Because BFS requires edges to be sorted by weight before running.

💡 Hint

Think about how BFS counts steps versus actual edge costs.

BFS counts the number of edges (steps) from start to node, assuming all edges cost the same. Weighted graphs need algorithms like Dijkstra that consider edge weights.

Practice

1. What does BFS (Breadth-First Search) help find in an unweighted graph?

easy

A. The longest path between two nodes

B. The node with the highest degree

C. The total number of nodes in the graph

D. The shortest path from a start node to all other 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, the first time it reaches a node is via the shortest path.

3. Final Answer:

   The shortest path from a start node to all other nodes -> Option D

4. Quick Check:

   BFS = shortest path in unweighted graph [OK]

Hint: BFS visits nodes by distance layers to find shortest paths [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds longest path
• Assuming BFS counts total nodes only

2. Which JavaScript data structure is best to implement the BFS queue for shortest path?

easy

A. Map to store node distances

B. Array with push and shift methods

C. Set to store unique nodes

D. Object with key-value pairs

Solution

1. Step 1: Identify BFS queue operations

   BFS requires adding nodes at the end and removing from the front, which is a queue behavior.

2. Step 2: Use Array methods for queue

   JavaScript arrays support push (add end) and shift (remove front), perfect for BFS queue.

3. Final Answer:

   Array with push and shift methods -> Option B

4. Quick Check:

   Queue = Array push/shift [OK]

Hint: Use array push/shift for BFS queue in JavaScript [OK]

Common Mistakes:

• Using Set as queue (no order guaranteed)
• Using Map for queue operations
• Using Object which has no order

3. What is the output distance array after running BFS from node 0 on this graph?

const graph = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 3],
  3: [1, 2, 4],
  4: [3]
};
// BFS from node 0

medium

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

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

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

D. [0, 2, 2, 3, 4]

Solution

1. Step 1: Initialize distances and start BFS

   Distance to start node 0 is 0. Neighbors 1 and 2 get distance 1.

2. Step 2: Visit neighbors of 1 and 2

   Node 3 is neighbor of 1 and 2, so distance is 2. Node 4 is neighbor of 3, distance 3.

3. Final Answer:

   [0, 1, 1, 2, 3] -> Option C

4. Quick Check:

   Distances = [0,1,1,2,3] [OK]

Hint: Distance increments by 1 each BFS layer [OK]

Common Mistakes:

• Assigning wrong distances to neighbors
• Mixing up node indices
• Forgetting to update distance only once

4. Identify the bug in this BFS shortest path code snippet:

function bfs(graph, start) {
  const queue = [];
  const distances = {};
  queue.push(start);
  distances[start] = 0;
  while (queue.length > 0) {
    const node = queue.pop();
    for (const neighbor of graph[node]) {
      if (!(neighbor in distances)) {
        distances[neighbor] = distances[node] + 1;
        queue.push(neighbor);
      }
    }
  }
  return distances;
}

medium

A. Using pop() instead of shift() causes wrong BFS order

B. Distances should be initialized with -1

C. Neighbors should be checked before pushing start node

D. Queue should be a Set to avoid duplicates

Solution

1. Step 1: Check queue operations in BFS

   BFS requires FIFO order, so nodes must be removed from front using shift(), not pop() which removes from end.

2. Step 2: Effect of using pop()

   Using pop() makes it LIFO, turning BFS into DFS order, breaking shortest path logic.

3. Final Answer:

   Using pop() instead of shift() causes wrong BFS order -> Option A

4. Quick Check:

   Queue removal must be shift() for BFS [OK]

Hint: Use shift() to dequeue in BFS, not pop() [OK]

Common Mistakes:

• Using pop() instead of shift() for queue
• Initializing distances incorrectly
• Using Set for queue which loses order

5. Given a graph with nodes 0 to 5 and edges: 0-1, 0-2, 1-3, 2-3, 3-4, 4-5, what is the shortest path from node 0 to node 5 using BFS?

hard

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

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

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

D. [0, 2, 4, 5]

Solution

1. Step 1: Explore neighbors from node 0

   Neighbors are 1 and 2, both distance 1.

2. Step 2: From neighbors, explore node 3

   Node 3 is neighbor of both 1 and 2, distance 2.

3. Step 3: From node 3, go to 4 then 5

   Node 4 distance 3, node 5 distance 4. The path via 1 is [0,1,3,4,5].

4. Final Answer:

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

5. Quick Check:

   Shortest path = [0,1,3,4,5] [OK]

Hint: Trace BFS layers from start to target [OK]

Common Mistakes:

• Choosing longer paths ignoring BFS order
• Skipping nodes in path
• Confusing edges and neighbors