Shortest Path in Unweighted Graph Using BFS in DSA Javascript - Build from Scratch

Shortest Path in Unweighted Graph Using BFS

📖 Scenario: You are working on a navigation app that helps users find the shortest route between places in a city. The city map is represented as a graph where intersections are nodes and roads are edges. Since all roads take the same time to cross, you want to find the shortest path from one intersection to another using a simple method.

🎯 Goal: Build a program that finds the shortest path between two intersections in an unweighted graph using Breadth-First Search (BFS). You will create the graph, set the start and end points, run BFS to find the shortest path, and then print the path.

📋 What You'll Learn

Create a graph as an adjacency list with exact nodes and edges

Set start and end nodes for the path search

Implement BFS to find the shortest path

Print the shortest path as a list of nodes

💡 Why This Matters

🌍 Real World

Finding shortest routes in maps, social networks, or any system where connections have equal cost.

💼 Career

Graph traversal and shortest path algorithms are fundamental in software engineering, especially in navigation, networking, and recommendation systems.

1

Create the graph as an adjacency list

Create a variable called graph as an object representing the city map with these exact connections:
'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']

DSA Javascript

# Create the graph variable as an adjacency list
# Your code here

Hint

Use an object where keys are node names and values are arrays of connected nodes.

2

Set the start and end nodes

Create two variables called startNode and endNode and set them to 'A' and 'F' respectively.

DSA Javascript

const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};

// Set startNode and endNode variables
# Your code here

Hint

Just create two constants with the exact names and values.

3

Implement BFS to find the shortest path

Write a function called findShortestPath that takes graph, startNode, and endNode as parameters and returns an array of nodes representing the shortest path from startNode to endNode using Breadth-First Search (BFS). Use a queue, a visited set, and a predecessors object to track the path.

DSA Javascript

const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};

const startNode = 'A';
const endNode = 'F';

// Write findShortestPath function below
# Your code here

Hint

Use a queue to explore nodes level by level, track visited nodes to avoid repeats, and store predecessors to build the path back.

4

Print the shortest path

Call findShortestPath(graph, startNode, endNode) and print the returned array using console.log.

DSA Javascript

const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};

const startNode = 'A';
const endNode = 'F';

function findShortestPath(graph, startNode, endNode) {
  const queue = [startNode];
  const visited = new Set([startNode]);
  const predecessors = {};

  while (queue.length > 0) {
    const current = queue.shift();
    if (current === endNode) {
      const path = [];
      let step = endNode;
      while (step !== undefined) {
        path.unshift(step);
        step = predecessors[step];
      }
      return path;
    }
    for (const neighbor of graph[current]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        predecessors[neighbor] = current;
        queue.push(neighbor);
      }
    }
  }
  return [];
}

// Print the shortest path below
# Your code here

Hint

Call the function with the graph, startNode, and endNode, then print the result.

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