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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS shortest path distances

What is the output of the following TypeScript code that finds shortest path distances from node 0 in an unweighted graph?

DSA Typescript

function bfsShortestPath(graph: number[][], start: number): number[] {
  const distances = Array(graph.length).fill(-1);
  const queue: number[] = [];
  distances[start] = 0;
  queue.push(start);
  while (queue.length > 0) {
    const node = queue.shift()!;
    for (const neighbor of graph[node]) {
      if (distances[neighbor] === -1) {
        distances[neighbor] = distances[node] + 1;
        queue.push(neighbor);
      }
    }
  }
  return distances;
}

const graph = [
  [1, 2],
  [0, 3],
  [0, 3],
  [1, 2, 4],
  [3]
];
console.log(bfsShortestPath(graph, 0));

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

B [0, 1, 1, 1, 2]

C [0, 2, 2, 3, 4]

D [0, 1, 1, 2, 3]

💡 Hint

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

The 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

Understanding BFS queue behavior

In BFS for shortest path in an unweighted graph, what is the main reason for using a queue data structure?

A To explore nodes in the order they are discovered, ensuring shortest path layers are processed first

B To store nodes in sorted order by their values

C To keep track of visited nodes using a stack-like behavior

D To randomly select the next node to explore

💡 Hint

Think about how BFS explores nodes level by level.

A queue ensures nodes are processed in the order they are discovered, which corresponds to increasing distance from the start node. This guarantees shortest path discovery in unweighted graphs.

🔧 Debug

advanced

Identify the bug in BFS shortest path code

What error will this TypeScript BFS shortest path code produce when run, and why?

DSA Typescript

function bfsShortestPath(graph: number[][], start: number): number[] {
  const distances = Array(graph.length).fill(-1);
  const queue: number[] = [];
  distances[start] = 0;
  queue.push(start);
  while (queue.length > 0) {
    const node = queue.pop()!;
    for (const neighbor of graph[node]) {
      if (distances[neighbor] === -1) {
        distances[neighbor] = distances[node] + 1;
        queue.push(neighbor);
      }
    }
  }
  return distances;
}

A TypeError because distances array is not initialized properly

B SyntaxError due to missing semicolon after queue.push(start)

C The code runs but returns incorrect distances because it uses pop() instead of shift() causing DFS behavior

D Runtime error because graph[node] is undefined

💡 Hint

Check how the queue is used to remove elements.

Using pop() removes the last element, making the traversal depth-first instead of breadth-first, so distances are incorrect for shortest path.

🚀 Application

advanced

Shortest path reconstruction from BFS distances

Given BFS distances from start node 0, how can you reconstruct the actual shortest path to node 4 in the graph below? Graph adjacency list: 0: [1, 2] 1: [0, 3] 2: [0, 3] 3: [1, 2, 4] 4: [3] Distances from 0: [0, 1, 1, 2, 3]

A Start from node 4 and move to any neighbor with distance one less until reaching 0, collecting nodes in reverse

B Start from node 0 and move to neighbors with larger distance until reaching 4

C Randomly pick neighbors until node 4 is reached

D Use a stack to store nodes visited during BFS and pop until node 4 is found

💡 Hint

Shortest path can be traced backward using distances.

By moving from the target node to neighbors with distance one less, you trace the shortest path back to the start node.

🧠 Conceptual

expert

Why BFS guarantees shortest path in unweighted graphs

Why does BFS always find the shortest path in an unweighted graph?

A Because BFS uses a stack to explore the deepest nodes first

B Because BFS explores nodes in order of increasing distance from the start node using a queue

C Because BFS sorts neighbors by their node values before visiting

D Because BFS uses recursion to explore all paths simultaneously

💡 Hint

Think about the order nodes are visited in BFS.

BFS visits nodes in layers based on their distance from the start node, so the first time a node is visited is via the shortest path.

Practice

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

easy

A. The shortest path from a start node to all other nodes

B. The heaviest edge in the graph

C. The longest path between two nodes

D. The total number of edges 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.

3. Final Answer:

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

4. Quick Check:

   BFS = shortest path in unweighted graph [OK]

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

Common Mistakes:

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

2. Which TypeScript data structure is best to use as a queue for BFS implementation?

easy

A. Array with push() and pop()

B. Array with push() and shift()

C. Set with add() and delete()

D. Map with set() and get()

Solution

1. Step 1: Identify queue operations needed for BFS

   BFS requires FIFO order: enqueue at end, dequeue from front.

2. Step 2: Choose Array methods matching FIFO

   push() adds to end, shift() removes from front, so Array with push() and shift() works as a queue.

3. Final Answer:

   Array with push() and shift() -> Option B

4. Quick Check:

   Queue = push + shift [OK]

Hint: Use push() to enqueue and shift() to dequeue in Array [OK]

Common Mistakes:

• Using pop() instead of shift() causes LIFO behavior
• Using Set or Map which don't maintain order
• Using Array methods incorrectly for queue

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

const graph = [[1,2],[0,3],[0,3],[1,2]];
// Nodes: 0,1,2,3
// Edges: 0-1, 0-2, 1-3, 2-3

medium

A. [0, 1, 1, 2]

B. [0, 2, 2, 3]

C. [1, 0, 1, 2]

D. [0, 1, 2, 1]

Solution

1. Step 1: Initialize distances and start BFS from node 0

   Distance to 0 is 0, others infinity initially.

2. Step 2: Visit neighbors level-wise

   Neighbors of 0 are 1 and 2, set distance 1 for both. Then neighbors of 1 and 2 include 3, set distance 2 for 3.

3. Final Answer:

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

4. Quick Check:

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

Hint: Distance increments by 1 per BFS level [OK]

Common Mistakes:

• Mixing up node indices and distances
• Assigning wrong distances to neighbors
• Confusing BFS with DFS order

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

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

medium

A. Neighbors are not checked for visited status

B. Distances array initialized with -1 instead of 0

C. Start node is not added to queue

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

Solution

1. Step 1: Check queue operations in BFS

   BFS requires FIFO queue, but pop() removes from end (LIFO).

2. Step 2: Identify impact of pop() usage

   Using pop() makes traversal DFS-like, breaking shortest path logic.

3. Final Answer:

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

4. Quick Check:

   Queue must be FIFO: push + shift [OK]

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

Common Mistakes:

• Confusing pop() with shift() for queue
• Ignoring visited check for neighbors
• Incorrect initialization of distances

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

hard

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

B. [0, 2, 3, 4]

C. [0, 1, 3, 4]

D. [0, 4]

Solution

1. Step 1: Explore neighbors from node 0

   Neighbors are 1 and 2, both distance 1.

2. Step 2: Explore neighbors of 1 and 2

   Both connect to 3 at distance 2.

3. Step 3: From 3, move to 4 at distance 3

   Shortest path is 0 -> 1 -> 3 -> 4 or 0 -> 2 -> 3 -> 4.

4. Step 4: Choose path found first by BFS

   BFS visits 1 before 2, so path is [0,1,3,4].

5. Final Answer:

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

6. Quick Check:

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

Hint: BFS finds shortest path by earliest discovered route [OK]

Common Mistakes:

• Assuming direct edge from 0 to 4 exists
• Choosing longer path ignoring BFS order
• Confusing path with distance array