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

Concept Flow - Why Shortest Path Is a Graph Problem Not a Tree Problem

Start: Need shortest path

↓

Is structure a Tree?

Yes→Unique path exists

↓

Shortest path = unique path

↓

Is structure a Graph?

Yes→Multiple paths possible

↓

Need algorithms like BFS/Dijkstra

↓

No path or invalid structure

↓

End

This flow shows that trees have unique paths between nodes, so shortest path is trivial, but graphs can have multiple paths, requiring shortest path algorithms.

Execution Sample

DSA Typescript

Graph:
A -- B
|    |
D -- C

Find shortest path A to C

This example shows multiple paths from A to C in a graph, illustrating why shortest path is a graph problem.

Execution Table

Step	Operation	Current Node	Visited Set	Queue	Action	Visual State
1	Start BFS	A	{}	[A]	Visit A, add neighbors B, D	A -> B, D; Visited: A
2	Visit next	B	{A}	[D, C]	Visit B, add neighbor C	A -> B -> C, D; Visited: A, B
3	Visit next	D	{A, B}	[C]	Visit D, add neighbor C (already queued)	A -> B -> C, D; Visited: A, B, D
4	Visit next	C	{A, B, D}	[]	Reached target C, stop	A -> B -> C; Visited: A, B, D, C
5	End	-	{A, B, D, C}	[]	Shortest path found: A -> B -> C	Final path: A -> B -> C

💡 Reached target node C at step 4, BFS stops with shortest path found.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	Final
Current Node	-	A	B	D	C	-
Visited Set	{}	{A}	{A, B}	{A, B, D}	{A, B, D, C}	{A, B, D, C}
Queue	[A]	[B, D]	[D, C]	[C]	[]	[]

Key Moments - 3 Insights

Why can't we use a tree structure to find the shortest path in this example?

Because the graph has multiple paths between nodes (see execution_table step 2 and 3), unlike a tree which has only one unique path between any two nodes.

Why does BFS stop when it reaches node C at step 4?

Because BFS explores nodes in order of distance from the start, the first time it reaches C is guaranteed to be the shortest path (execution_table step 4).

Why do we keep track of a visited set during BFS?

To avoid revisiting nodes and prevent infinite loops in graphs with cycles, as shown in variable_tracker where visited nodes grow each step.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, which nodes are in the queue?

A [A, B]

B [B, D]

C [D, C]

D [B, C]

💡 Hint

Check the 'Queue' column in execution_table row with Step 2.

At which step does BFS first visit the target node C?

A Step 3

B Step 4

C Step 5

D Step 2

💡 Hint

Look at the 'Current Node' and 'Action' columns in execution_table.

If the graph was a tree, how would the shortest path search change?

A The shortest path would be unique and no BFS needed

B We would need to track visited nodes to avoid cycles

C There would be multiple paths to check

D The queue would contain all nodes at once

💡 Hint

Refer to concept_flow where trees have unique paths.

Concept Snapshot

Shortest path problems arise in graphs because multiple paths can exist between nodes.
Trees have unique paths, so shortest path is trivial.
Graphs require algorithms like BFS or Dijkstra to find shortest paths.
Tracking visited nodes prevents cycles and infinite loops.
BFS finds shortest path by exploring nodes in order of distance.

Full Transcript

Shortest path is a graph problem because graphs can have many paths between two points, unlike trees which have only one unique path. In the example graph with nodes A, B, C, and D, BFS explores neighbors level by level, visiting A first, then B and D, and finally reaching C. The visited set keeps track of nodes already checked to avoid loops. BFS stops when it reaches the target node C, ensuring the shortest path is found. Trees do not require such algorithms because their structure guarantees a single path between nodes.

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