Shortest Path in Unweighted Graph Using BFS in DSA Javascript

Mental Model

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

Analogy: Imagine you are in a maze and shout to find the shortest way out. Your shout reaches nearby friends first, then their friends, spreading out evenly until someone finds the exit.

Graph nodes connected:
0 -> 1 -> 2
↓    ↓
3 -> 4
Start at node 0, find shortest path to node 4.

Dry Run Walkthrough

Input: Graph edges: 0-1, 0-3, 1-2, 1-4, 3-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

Queue: [0↑]
Distances: {0:0, 1:∞, 2:∞, 3:∞, 4:∞}

Why: We begin from the start node with distance zero

Step 2: Visit neighbors of 0: nodes 1 and 3, set distance 1

Queue: [1↑, 3]
Distances: {0:0, 1:1, 2:∞, 3:1, 4:∞}

Why: Neighbors of start are one step away

Step 3: Dequeue node 1, visit neighbors 2 and 4, set distance 2

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

Why: From node 1, neighbors are two steps from start

Step 4: Dequeue node 3, visit neighbor 4 but already visited

Queue: [2↑, 4]
Distances unchanged

Why: Node 4 already has shortest distance, no update

Step 5: Dequeue node 2, no new neighbors

Queue: [4↑]

Why: No new nodes to visit from 2

Step 6: Dequeue node 4, destination reached

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

Why: Found shortest path distance to node 4

Result:

Shortest path distance from 0 to 4 is 2

Annotated Code

DSA Javascript

class Graph {
  constructor(vertices) {
    this.vertices = vertices;
    this.adjList = new Map();
    for (let i = 0; i < vertices; i++) {
      this.adjList.set(i, []);
    }
  }

  addEdge(u, v) {
    this.adjList.get(u).push(v);
    this.adjList.get(v).push(u);
  }

  shortestPathBFS(start, end) {
    const distances = Array(this.vertices).fill(Infinity);
    const queue = [];
    distances[start] = 0;
    queue.push(start);

    while (queue.length > 0) {
      const current = queue.shift(); // dequeue
      if (current === end) {
        return distances[end];
      }
      for (const neighbor of this.adjList.get(current)) {
        if (distances[neighbor] === Infinity) {
          distances[neighbor] = distances[current] + 1;
          queue.push(neighbor);
        }
      }
    }
    return -1; // no path found
  }
}

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

const startNode = 0;
const endNode = 4;
const shortestDistance = graph.shortestPathBFS(startNode, endNode);
console.log(`Shortest path distance from ${startNode} to ${endNode} is ${shortestDistance}`);

distances[start] = 0;

Initialize start node distance to zero

queue.push(start);

Add start node to queue to begin BFS

const current = queue.shift();

Remove front node from queue to explore neighbors

if (current === end) { return distances[end]; }

Stop search when destination node is reached

for (const neighbor of this.adjList.get(current)) {

Check all neighbors of current node

if (distances[neighbor] === Infinity) {

Visit neighbor only if not visited before

distances[neighbor] = distances[current] + 1;

Update neighbor distance as one more than current

queue.push(neighbor);

Add neighbor to queue for future exploration

Output

Shortest path distance from 0 to 4 is 2

Complexity Analysis

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

Space: O(V) for the distances 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

No path exists between start and end

Function returns -1 indicating no path found

DSA Javascript

if (current === end) { return distances[end]; }

Start and end nodes are the same

Distance returned is 0 immediately

DSA Javascript

distances[start] = 0;

Graph with isolated nodes

Distances remain Infinity for unreachable nodes, returns -1 if end unreachable

DSA Javascript

if (distances[neighbor] === Infinity) {

When to Use This Pattern

When asked for shortest path in an unweighted graph, use BFS because it explores nodes in order of distance from start, guaranteeing shortest path.

Common Mistakes

Mistake: Not marking nodes as visited leads to infinite loops or repeated visits
Fix: Use a distances array or visited set to track visited nodes before enqueueing

Mistake: Returning distance before checking all neighbors can miss shorter paths
Fix: Return distance only when dequeuing the destination node

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 level by level, ensuring the first time you reach the target is the shortest path.

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