Why Shortest Path Is a Graph Problem Not a Tree Problem in DSA Typescript - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why can't shortest path algorithms be limited to trees?

Which reason best explains why shortest path problems require graph structures rather than just trees?

A Because trees do not have cycles, but shortest paths must consider cycles to find the shortest route.

B Because trees always have multiple paths between nodes, making shortest path trivial.

C Because trees have weighted edges, but graphs do not support weights.

D Because shortest path algorithms only work on disconnected nodes, which trees do not have.

💡 Hint

Think about the presence of cycles and multiple paths in graphs versus trees.

Trees are a special type of graph without cycles. Shortest path problems often require handling cycles and multiple paths between nodes, which only general graphs can represent.

❓ Predict Output

intermediate

Output of shortest path on a tree vs graph

What is the output of the following TypeScript code that tries to find the shortest path in a tree and a graph?

DSA Typescript

type Edge = { to: number; weight: number };

const tree: Edge[][] = [
  [{ to: 1, weight: 2 }],
  [{ to: 0, weight: 2 }, { to: 2, weight: 3 }],
  [{ to: 1, weight: 3 }]
];

const graph: Edge[][] = [
  [{ to: 1, weight: 2 }, { to: 2, weight: 4 }],
  [{ to: 0, weight: 2 }, { to: 2, weight: 1 }],
  [{ to: 0, weight: 4 }, { to: 1, weight: 1 }]
];

function dijkstra(graph: Edge[][], start: number): number[] {
  const dist = Array(graph.length).fill(Infinity);
  dist[start] = 0;
  const visited = new Set<number>();

  while (visited.size < graph.length) {
    let u = -1;
    let minDist = Infinity;
    for (let i = 0; i < dist.length; i++) {
      if (!visited.has(i) && dist[i] < minDist) {
        minDist = dist[i];
        u = i;
      }
    }
    if (u === -1) break;
    visited.add(u);

    for (const edge of graph[u]) {
      if (dist[u] + edge.weight < dist[edge.to]) {
        dist[edge.to] = dist[u] + edge.weight;
      }
    }
  }
  return dist;
}

const treeDistances = dijkstra(tree, 0);
const graphDistances = dijkstra(graph, 0);

console.log(JSON.stringify({ treeDistances, graphDistances }));

A {"treeDistances":[0,2,5],"graphDistances":[0,4,3]}

B {"treeDistances":[0,2,4],"graphDistances":[0,3,3]}

C {"treeDistances":[0,2,5],"graphDistances":[0,2,3]}

D {"treeDistances":[0,3,5],"graphDistances":[0,2,4]}

💡 Hint

Trace the shortest distances from node 0 to others in both structures.

The tree has a single path from 0 to 2 through 1 with weights 2 and 3, totaling 5. The graph has a shorter path from 0 to 2 directly or via 1 with total weight 3.

🔧 Debug

advanced

Identify the error in shortest path code for graphs with cycles

What error will this TypeScript code produce when running Dijkstra's algorithm on a graph with negative weight edges?

DSA Typescript

type Edge = { to: number; weight: number };

const graph: Edge[][] = [
  [{ to: 1, weight: 1 }],
  [{ to: 0, weight: 1 }, { to: 2, weight: -2 }],
  [{ to: 1, weight: -2 }]
];

function dijkstra(graph: Edge[][], start: number): number[] {
  const dist = Array(graph.length).fill(Infinity);
  dist[start] = 0;
  const visited = new Set<number>();

  while (visited.size < graph.length) {
    let u = -1;
    let minDist = Infinity;
    for (let i = 0; i < dist.length; i++) {
      if (!visited.has(i) && dist[i] < minDist) {
        minDist = dist[i];
        u = i;
      }
    }
    if (u === -1) break;
    visited.add(u);

    for (const edge of graph[u]) {
      if (dist[u] + edge.weight < dist[edge.to]) {
        dist[edge.to] = dist[u] + edge.weight;
      }
    }
  }
  return dist;
}

console.log(dijkstra(graph, 0));

A The code runs correctly and returns valid shortest distances.

B The code throws a runtime error because of negative weights.

C The code enters an infinite loop because of cycles.

D The algorithm produces incorrect shortest distances due to negative edge weights.

💡 Hint

Dijkstra's algorithm does not handle negative weights properly.

Dijkstra's algorithm assumes all edge weights are non-negative. Negative weights can cause it to produce incorrect results because it may finalize distances too early.

📝 Syntax

advanced

Identify the syntax error in this graph adjacency list declaration

Which option contains a syntax error in declaring a graph adjacency list in TypeScript?

DSA Typescript

type Edge = { to: number; weight: number };

const graph: Edge[][] = [
  [{ to: 1, weight: 2 }, { to: 2, weight: 3 }],
  [{ to: 0, weight: 2 }, { to: 2, weight: 4 }],
  [{ to: 0, weight: 3 }, { to: 1, weight: 4 }]
];

A const graph: Edge[][] = [ [{ to: 1, weight: 2 }, { to: 2, weight: 3 }], [{ to: 0, weight: 2 }, { to: 2, weight: 4 }], [{ to: 0, weight: 3 }, { to: 1, weight: 4 }] );

B const graph: Edge[][] = [ [{ to: 1, weight: 2 }, { to: 2, weight: 3 }], [{ to: 0, weight: 2 }, { to: 2, weight: 4 }], [{ to: 0, weight: 3 }, { to: 1, weight: 4 }] ];

C ;] ]} 4 :thgiew ,1 :ot { ,} 3 :thgiew ,0 :ot {[ ,]} 4 :thgiew ,2 :ot { ,} 2 :thgiew ,0 :ot {[ ,]} 3 :thgiew ,2 :ot { ,} 2 :thgiew ,1 :ot {[ [ = ][][egdE :hparg tsnoc

D onst graph: Edge[][] = [ [{ to: 1, weight: 2 }, { to: 2, weight: 3 }], [{ to: 0, weight: 2 }, { to: 2, weight: 4 }], [{ to: 0, weight: 3 }, { to: 1, weight: 4 }] ];

💡 Hint

Check the brackets and parentheses carefully.

Option A ends the array with a closing parenthesis ')' instead of a closing bracket ']'. This causes a syntax error.

🚀 Application

expert

Why is shortest path more complex in graphs than trees?

Which statement best explains why shortest path algorithms are more complex in graphs than in trees?

A Trees have weighted edges that change dynamically, making shortest path calculations simpler.

B Graphs can have cycles and multiple paths between nodes, requiring algorithms to handle revisiting nodes and updating distances.

C Graphs always have fewer nodes than trees, so shortest path is faster in graphs.

D Trees allow negative edge weights, which graphs do not support, simplifying shortest path in trees.

💡 Hint

Consider how cycles and multiple paths affect pathfinding.

Graphs can have cycles and multiple paths, so shortest path algorithms must carefully track and update distances to avoid incorrect results. Trees have a unique path between nodes, making shortest path simpler.

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