Shortest Path in Unweighted Graph Using BFS in DSA Typescript

Mental Model

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

Analogy: Imagine you are in a maze and shout out loud. The sound reaches rooms closest to you first, then rooms further away. The first time the sound reaches a room is the shortest path to that room.

Graph nodes connected:
0 -> 1 -> 3
↓    ↓
2    4

Start at node 0, explore neighbors 1 and 2 first, then their neighbors.

Dry Run Walkthrough

Input: Graph edges: 0-1, 0-2, 1-3, 1-4; Find shortest path from 0 to 4

Goal: Find the shortest path length and the path itself from node 0 to node 4

Step 1: Start BFS from node 0, mark distance 0

Queue: [0]
Distances: {0:0}
Parents: {0:null}

Why: We begin from the start node with distance zero

Step 2: Dequeue 0, enqueue neighbors 1 and 2 with distance 1

Queue: [1, 2]
Distances: {0:0, 1:1, 2:1}
Parents: {0:null, 1:0, 2:0}

Why: Neighbors of 0 are one step away

Step 3: Dequeue 1, enqueue neighbors 3 and 4 with distance 2

Queue: [2, 3, 4]
Distances: {0:0, 1:1, 2:1, 3:2, 4:2}
Parents: {0:null, 1:0, 2:0, 3:1, 4:1}

Why: Neighbors of 1 are two steps away from start

Step 4: Dequeue 2, no new neighbors to enqueue

Queue: [3, 4]
Distances unchanged
Parents unchanged

Why: Node 2 has no unvisited neighbors

Step 5: Dequeue 3, no new neighbors to enqueue

Queue: [4]
Distances unchanged
Parents unchanged

Why: Node 3 has no unvisited neighbors

Step 6: Dequeue 4, target found at distance 2

Queue: []
Distances: {0:0,1:1,2:1,3:2,4:2}
Parents unchanged

Why: Reached target node, shortest path found

Result:

Shortest path length: 2
Path: 0 -> 1 -> 4

Annotated Code

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]>;

  constructor() {
    this.adjacencyList = new Map();
  }

  addEdge(u: number, v: number) {
    if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
    if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
    this.adjacencyList.get(u)!.push(v);
    this.adjacencyList.get(v)!.push(u);
  }

  shortestPathBFS(start: number, target: number): {distance: number, path: number[]} {
    const queue: number[] = [];
    const distances: Map<number, number> = new Map();
    const parents: Map<number, number | null> = new Map();

    queue.push(start);
    distances.set(start, 0);
    parents.set(start, null);

    while (queue.length > 0) {
      const current = queue.shift()!;
      if (current === target) break;

      for (const neighbor of this.adjacencyList.get(current) || []) {
        if (!distances.has(neighbor)) {
          queue.push(neighbor); // enqueue neighbor
          distances.set(neighbor, distances.get(current)! + 1); // set distance
          parents.set(neighbor, current); // track path
        }
      }
    }

    if (!distances.has(target)) {
      return { distance: -1, path: [] };
    }

    const path: number[] = [];
    let node: number | null = target;
    while (node !== null) {
      path.push(node);
      node = parents.get(node) || null;
    }
    path.reverse();

    return { distance: distances.get(target)!, path };
  }
}

// Driver code
const graph = new Graph();
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);

const result = graph.shortestPathBFS(0, 4);
console.log(`Shortest path length: ${result.distance}`);
console.log(`Path: ${result.path.join(' -> ')}`);

queue.push(start); distances.set(start, 0); parents.set(start, null);

Initialize BFS with start node distance zero and no parent

const current = queue.shift()!; if (current === target) break;

Dequeue node and stop if target found

for (const neighbor of this.adjacencyList.get(current) || []) { if (!distances.has(neighbor)) { queue.push(neighbor); distances.set(neighbor, distances.get(current)! + 1); parents.set(neighbor, current); } }

Enqueue unvisited neighbors, set their distance and parent

if (!distances.has(target)) { return { distance: -1, path: [] }; }

Handle case when target is unreachable

while (node !== null) { path.push(node); node = parents.get(node) || null; } path.reverse();

Reconstruct path from target to start using parents

Output

Shortest path length: 2

Path: 0 -> 1 -> 4

Complexity Analysis

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

Space: O(V) for storing distances, parents, and the queue

vs Alternative: Compared to DFS, BFS guarantees shortest path in unweighted graphs with similar time but DFS may not find shortest path

Edge Cases

Start node equals target node

Distance is zero and path contains only the start node

DSA Typescript

if (current === target) break;

Target node unreachable from start

Returns distance -1 and empty path

DSA Typescript

if (!distances.has(target)) {
  return { distance: -1, path: [] };
}

Graph with isolated nodes

Isolated nodes are never visited, so unreachable targets handled correctly

DSA Typescript

for (const neighbor of this.adjacencyList.get(current) || [])

When to Use This Pattern

When you need the shortest path in a graph without weights, use BFS because it explores nodes in order of distance from the start.

Common Mistakes

Mistake: Not marking nodes as visited before enqueueing causes repeated visits and infinite loops
Fix: Mark nodes as visited (set distance) immediately when enqueueing

Mistake: Using DFS instead of BFS for shortest path in unweighted graph
Fix: Use BFS because it guarantees shortest path by level order traversal

Summary

Finds shortest path in an unweighted graph using breadth-first search.

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

BFS explores neighbors level by level, ensuring the first time you reach a node is 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