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

Shortest Path in Unweighted Graph Using BFS

📖 Scenario: Imagine you are navigating a city with intersections connected by roads. You want to find the shortest number of roads to travel from one intersection to another.

🎯 Goal: You will build a program that finds the shortest path length between two intersections in an unweighted graph using Breadth-First Search (BFS).

📋 What You'll Learn

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

Set up start and end nodes for the path search

Implement BFS to find the shortest path length

Print the shortest path length or -1 if no path exists

💡 Why This Matters

🌍 Real World

Finding shortest routes in maps, social networks, or network routing where all connections have equal cost.

💼 Career

Understanding BFS and shortest path algorithms is essential for software engineers working on navigation, recommendation systems, and network analysis.

1

Create the graph as an adjacency list

Create a variable called graph as a Map<string, string[]> with these exact entries: 'A' connected to ['B', 'C'], 'B' connected to ['A', 'D', 'E'], 'C' connected to ['A', 'F'], 'D' connected to ['B'], 'E' connected to ['B', 'F'], and 'F' connected to ['C', 'E'].

DSA Typescript

// Your code here

Hint

Use new Map() with an array of key-value pairs where keys are node names and values are arrays of connected nodes.

2

Set start and end nodes

Create two variables: start set to 'A' and end set to 'F'.

DSA Typescript

const graph: Map = new Map([
  ['A', ['B', 'C']],
  ['B', ['A', 'D', 'E']],
  ['C', ['A', 'F']],
  ['D', ['B']],
  ['E', ['B', 'F']],
  ['F', ['C', 'E']]
]);
// Your code here

Hint

Just create two string variables with the exact names and values.

3

Implement BFS to find shortest path length

Write a function called shortestPathLength that takes graph, start, and end as parameters and returns the shortest path length as a number. Use a queue for BFS, a Set called visited to track visited nodes, and a Map called distance to store distances from start. Return -1 if end is not reachable.

DSA Typescript

const graph: Map = new Map([
  ['A', ['B', 'C']],
  ['B', ['A', 'D', 'E']],
  ['C', ['A', 'F']],
  ['D', ['B']],
  ['E', ['B', 'F']],
  ['F', ['C', 'E']]
]);

const start: string = 'A';
const end: string = 'F';

// Your code here

Hint

Use a queue to explore nodes level by level. Track visited nodes to avoid repeats. Store distance from start for each node. Return distance when you reach the end.

4

Print the shortest path length

Call shortestPathLength(graph, start, end) and print the result using console.log.

DSA Typescript

const graph: Map = new Map([
  ['A', ['B', 'C']],
  ['B', ['A', 'D', 'E']],
  ['C', ['A', 'F']],
  ['D', ['B']],
  ['E', ['B', 'F']],
  ['F', ['C', 'E']]
]);

const start: string = 'A';
const end: string = 'F';

function shortestPathLength(graph: Map, start: string, end: string): number {
  const queue: string[] = [];
  const visited: Set = new Set();
  const distance: Map = new Map();

  queue.push(start);
  visited.add(start);
  distance.set(start, 0);

  while (queue.length > 0) {
    const current = queue.shift()!;
    if (current === end) {
      return distance.get(current)!;
    }
    const neighbors = graph.get(current) || [];
    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        distance.set(neighbor, (distance.get(current) || 0) + 1);
        queue.push(neighbor);
      }
    }
  }

  return -1;
}

// Your code here

Hint

Call the function with the graph, start, and end nodes, then print the returned number.