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.

Practice

1. Why is finding the shortest path usually considered a graph problem rather than a tree problem?

easy

A. Because shortest path algorithms only work on trees.

B. Because trees do not have nodes or edges.

C. Because trees always have negative edge weights.

D. Because graphs can have cycles and multiple paths between nodes, unlike trees.

Solution

1. Step 1: Understand the structure of trees and graphs

   Trees are a special type of graph with no cycles and exactly one path between any two nodes.

2. Step 2: Analyze shortest path requirements

   Shortest path problems require handling multiple paths and cycles, which only general graphs can have.

3. Final Answer:

   Because graphs can have cycles and multiple paths between nodes, unlike trees. -> Option D

4. Quick Check:

   Graphs allow multiple paths [OK]

Hint: Shortest path needs multiple paths; trees have only one [OK]

Common Mistakes:

• Thinking trees have cycles
• Assuming shortest path only applies to trees
• Confusing nodes and edges in trees

2. Which of the following TypeScript code snippets correctly declares a graph adjacency list for shortest path calculation?

easy

A. const graph: Map = new Map();

B. const graph: number[][] = []; graph[0] = 1;

C. const graph: string = 'adjacency list';

D. const graph: number = 0;

Solution

1. Step 1: Identify correct graph adjacency list type

   An adjacency list for a graph is best represented as a Map from node to array of connected nodes.

2. Step 2: Check code correctness

   const graph: Map = new Map(); uses Map which is correct. const graph: number[][] = []; graph[0] = 1; assigns a number to an array index incorrectly. Options C and D use wrong types.

3. Final Answer:

   const graph: Map<number, number[]> = new Map(); -> Option A

4. Quick Check:

   Map with arrays [OK]

Hint: Use Map for adjacency lists [OK]

Common Mistakes:

• Using wrong data types for graph
• Assigning values directly to array index without initialization
• Confusing string or number types for graph

3. Given the following graph represented as adjacency list, what is the shortest path distance from node 0 to node 3?

const graph = new Map([
  [0, [1, 2]],
  [1, [2, 3]],
  [2, [3]],
  [3, []]
]);

// Assume each edge has weight 1
// Use BFS to find shortest path distance

medium

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Trace BFS from node 0 to node 3

   From 0, neighbors are 1 and 2 (distance 1). From 1, neighbors include 3 (distance 2). From 2, neighbor is 3 (distance 2).

2. Step 2: Determine shortest distance

   Shortest path is 0 -> 1 -> 3 or 0 -> 2 -> 3, both length 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Shortest path length = 2 [OK]

Hint: BFS finds shortest path in unweighted graph [OK]

Common Mistakes:

• Counting edges incorrectly
• Confusing path length with number of nodes
• Ignoring multiple paths

4. Identify the bug in this TypeScript code snippet for shortest path in a graph and select the fix:

function shortestPath(graph: Map, start: number, end: number): number {
  const queue: number[] = [start];
  const distances: Map = new Map();
  distances.set(start, 0);

  while (queue.length > 0) {
    const node = queue.shift();
    for (const neighbor of graph.get(node)!) {
      if (!distances.has(neighbor)) {
        distances.set(neighbor, distances.get(node)! + 1);
        queue.push(neighbor);
      }
    }
  }
  return distances.get(end)!;
}

medium

A. Change queue.shift() to queue.pop() to get correct order.

B. Remove the exclamation marks (!) to avoid errors.

C. Add check if node is undefined after shift before using it.

D. Initialize distances with Infinity for all nodes before starting.

Solution

1. Step 1: Analyze queue.shift() usage

   queue.shift() can return undefined if queue is empty, but loop condition prevents that. However, TypeScript needs explicit check for undefined.

2. Step 2: Fix by checking node is not undefined

   Adding a check after shift ensures safe usage of node in graph.get(node).

3. Final Answer:

   Add check if node is undefined after shift before using it. -> Option C

4. Quick Check:

   Check for undefined after shift [OK]

Hint: Always check shift() result before use in TypeScript [OK]

Common Mistakes:

• Using pop() breaks BFS order
• Ignoring possible undefined from shift()
• Misunderstanding exclamation mark usage

5. You want to find the shortest path in a network where some edges have negative weights but no negative cycles. Why is this a graph problem and which algorithm suits best?

hard

A. Because graphs can have cycles and negative edges; use Bellman-Ford algorithm.

B. Because trees cannot have negative weights; use Dijkstra's algorithm.

C. Because trees always have positive weights; use BFS.

D. Because graphs with negative edges are invalid; no algorithm applies.

Solution

1. Step 1: Understand edge weights and graph structure

   Negative edge weights and cycles can only appear in graphs, not trees.

2. Step 2: Choose suitable algorithm

   Dijkstra's algorithm fails with negative edges; Bellman-Ford handles negative weights and detects negative cycles.

3. Final Answer:

   Because graphs can have cycles and negative edges; use Bellman-Ford algorithm. -> Option A

4. Quick Check:

   Negative edges + cycles = Bellman-Ford [OK]

Hint: Negative edges? Use Bellman-Ford on graphs [OK]

Common Mistakes:

• Using Dijkstra with negative edges
• Thinking trees can have negative edges
• Assuming no algorithm works with negative edges