Why Shortest Path Is a Graph Problem Not a Tree Problem in DSA Typescript - See It Work

Why Shortest Path Is a Graph Problem Not a Tree Problem

📖 Scenario: Imagine you are planning a trip in a city. The city map has many roads connecting different places. You want to find the shortest way to get from your home to a park.This is like finding the shortest path in a network of roads. Roads can connect places in many ways, sometimes with loops or multiple routes.

🎯 Goal: You will create a simple map using a graph data structure, then find the shortest path from one place to another. This will show why shortest path problems need graphs, not just trees.

📋 What You'll Learn

Create a graph using an adjacency list to represent places and roads

Add a starting point variable for the path search

Implement a simple shortest path search using breadth-first search (BFS)

Print the shortest path found from start to destination

💡 Why This Matters

🌍 Real World

Finding shortest routes in maps, network routing, social network connections, and many other real-world problems use graphs.

💼 Career

Understanding graphs and shortest path algorithms is essential for software engineers working in navigation, logistics, networking, and data analysis.

1

Create the graph as an adjacency list

Create a constant called graph as an object with these exact keys and values: 'Home': ['Cafe', 'Library'], 'Cafe': ['Home', 'Park'], 'Library': ['Home', 'Park'], 'Park': ['Cafe', 'Library']

DSA Typescript

// Your code here

Hint

Use an object where each key is a place and the value is an array of connected places.

2

Add the starting point variable

Create a constant called start and set it to the string 'Home'

DSA Typescript

const graph: { [key: string]: string[] } = {
  'Home': ['Cafe', 'Library'],
  'Cafe': ['Home', 'Park'],
  'Library': ['Home', 'Park'],
  'Park': ['Cafe', 'Library']
};

// Your code here

Hint

Just create a constant with the exact name and value.

3

Implement BFS to find the shortest path

Create a function called findShortestPath that takes graph, start, and end as parameters and returns an array of strings representing the shortest path. Use a queue and a visited set to perform breadth-first search. Return the path from start to end.

DSA Typescript

const graph: { [key: string]: string[] } = {
  'Home': ['Cafe', 'Library'],
  'Cafe': ['Home', 'Park'],
  'Library': ['Home', 'Park'],
  'Park': ['Cafe', 'Library']
};

const start = 'Home';

// Your code here

Hint

Use a queue to keep paths to explore and a set to track visited places. Add neighbors to the queue with the current path extended.

4

Print the shortest path from Home to Park

Call findShortestPath with graph, start, and 'Park' as arguments. Store the result in a constant called shortestPath. Then print shortestPath.join(' -> ') to show the path as a string.

DSA Typescript

const graph: { [key: string]: string[] } = {
  'Home': ['Cafe', 'Library'],
  'Cafe': ['Home', 'Park'],
  'Library': ['Home', 'Park'],
  'Park': ['Cafe', 'Library']
};

const start = 'Home';

function findShortestPath(graph: { [key: string]: string[] }, start: string, end: string): string[] {
  const queue: string[][] = [[start]];
  const visited = new Set([start]);

  while (queue.length > 0) {
    const path = queue.shift()!;
    const node = path[path.length - 1];

    if (node === end) {
      return path;
    }

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([...path, neighbor]);
      }
    }
  }

  return [];
}

// Your code here

Hint

Call the function with the right arguments, save the result, and print it joined by arrows.