Why Shortest Path Is a Graph Problem Not a Tree Problem in DSA Typescript - Why This Pattern

Mental Model

Shortest path means finding the quickest way between two points when many routes exist. Trees have only one path between points, but graphs can have many paths and loops.

Analogy: Imagine city streets (graph) versus a family tree (tree). In a family tree, you can only go one way between relatives. In city streets, you can take many routes and shortcuts to reach a place faster.

Tree:
  1
 / \
2   3

Graph:
1 -> 2 -> 3
↑    ↓   ↑
4 ← 5 ← 6

Dry Run Walkthrough

Input: Graph with nodes 1,2,3,4 and edges: 1->2, 2->3, 1->4, 4->3; find shortest path from 1 to 3

Goal: Show why shortest path needs graph logic because multiple paths exist

Step 1: Check path 1->2->3

Paths checked: [1->2->3]
Distance: 2 edges

Why: This is one possible path from 1 to 3

Step 2: Check path 1->4->3

Paths checked: [1->2->3, 1->4->3]
Distance: 2 edges

Why: Another path exists with same length

Step 3: Compare paths and confirm shortest distance is 2 edges

Shortest path length: 2 edges
Paths: 1->2->3 or 1->4->3

Why: Multiple shortest paths exist, showing graph complexity

Result:

Shortest paths: 1->2->3 and 1->4->3 with length 2 edges

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, []);
    this.adjacencyList.get(u)!.push(v);
  }

  shortestPath(start: number, end: number): number[] | null {
    const queue: number[] = [start];
    const visited = new Set<number>([start]);
    const parent = new Map<number, number | null>();
    parent.set(start, null);

    while (queue.length > 0) {
      const node = queue.shift()!;
      if (node === end) {
        const path: number[] = [];
        let curr: number | null = end;
        while (curr !== null) {
          path.unshift(curr);
          curr = parent.get(curr)!;
        }
        return path;
      }

      for (const neighbor of this.adjacencyList.get(node) || []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          parent.set(neighbor, node);
          queue.push(neighbor);
        }
      }
    }
    return null;
  }
}

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

const path = graph.shortestPath(1, 3);
if (path) {
  console.log(path.join(' -> '));
} else {
  console.log('No path found');
}

const queue: number[] = [start];

Initialize queue with start node for BFS traversal

const visited = new Set<number>([start]);

Mark start node as visited to avoid revisiting

while (queue.length > 0) {

Process nodes level by level until queue is empty

const node = queue.shift()!;

Dequeue current node to explore neighbors

if (node === end) { ... }

If end node reached, reconstruct path using parent map

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

Explore all neighbors of current node

if (!visited.has(neighbor)) { ... }

Visit unvisited neighbors, mark visited, and enqueue

Output

1 -> 2 -> 3

Complexity Analysis

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

Space: O(V) for queue, visited set, and parent map storing nodes

vs Alternative: Unlike trees with single paths, graphs require BFS to explore multiple routes, increasing complexity

Edge Cases

No path exists between start and end

Function returns null indicating no path found

DSA Typescript

if (node === end) { ... } and return null at end of shortestPath

Start node equals end node

Returns path with single node immediately

DSA Typescript

if (node === end) { ... }

Graph with cycles

Visited set prevents infinite loops by skipping visited nodes

DSA Typescript

if (!visited.has(neighbor)) { ... }

When to Use This Pattern

When a problem asks for shortest routes with multiple possible paths or loops, recognize it as a graph problem needing BFS or Dijkstra, not a tree problem.

Common Mistakes

Mistake: Assuming only one path exists like in trees and using DFS without tracking shortest distance
Fix: Use BFS to explore all paths level by level to find shortest path

Mistake: Not marking visited nodes causing infinite loops in cyclic graphs
Fix: Maintain a visited set to skip already explored nodes

Summary

It finds the shortest route between two points in a structure where many paths and loops exist.

Use it when multiple routes or cycles can connect points, like in maps or networks.

The key insight is that graphs can have many paths, so you must explore all efficiently to find the shortest.