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.