Shortest Path in DAG Using Topological Order in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of shortest path distances after topological order processing

Given the following TypeScript code that finds shortest paths in a Directed Acyclic Graph (DAG) using topological order, what is the printed output array representing shortest distances from source node 0?

DSA Typescript

type Edge = [number, number, number];

function shortestPathDAG(n: number, edges: Edge[], src: number): number[] {
  const graph: Map<number, [number, number][]> = new Map();
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [u, v, w] of edges) {
    graph.get(u)!.push([v, w]);
  }

  const visited = new Array(n).fill(false);
  const stack: number[] = [];

  function dfs(node: number) {
    visited[node] = true;
    for (const [nbr] of graph.get(node)!) {
      if (!visited[nbr]) dfs(nbr);
    }
    stack.push(node);
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) dfs(i);
  }

  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;

  while (stack.length) {
    const node = stack.pop()!;
    if (dist[node] !== Infinity) {
      for (const [nbr, w] of graph.get(node)!) {
        if (dist[node] + w < dist[nbr]) {
          dist[nbr] = dist[node] + w;
        }
      }
    }
  }

  return dist;
}

const n = 6;
const edges: Edge[] = [
  [0, 1, 5],
  [0, 2, 3],
  [1, 3, 6],
  [1, 2, 2],
  [2, 4, 4],
  [2, 5, 2],
  [2, 3, 7],
  [3, 4, -1],
  [4, 5, -2]
];

console.log(shortestPathDAG(n, edges, 0));

A [0, 5, 3, 13, 12, 10]

B [0, 5, 3, 11, 10, 8]

C [0, 5, 3, 10, 7, 5]

D [0, 5, 3, 10, 9, 7]

💡 Hint

Trace the graph edges and update distances in topological order starting from source 0.

The algorithm first finds a topological order of nodes. Then it initializes distances with Infinity except source 0. It relaxes edges in topological order, updating shortest distances. Negative weights are allowed but no cycles exist. The final distances array is [0, 5, 3, 10, 7, 5].

🧠 Conceptual

intermediate

Why does topological order help in shortest path for DAG?

Why is using topological order important when finding shortest paths in a Directed Acyclic Graph (DAG)?

A Because it detects cycles in the graph to prevent infinite loops.

B Because it ensures nodes are processed only after all their predecessors, allowing correct distance updates without revisiting nodes.

C Because it sorts nodes by their distance values automatically.

D Because it guarantees the graph is weighted positively.

💡 Hint

Think about how processing nodes in order affects distance relaxation.

Topological order processes nodes so that all edges from earlier nodes to later nodes are relaxed in one pass. This avoids revisiting nodes multiple times and ensures shortest paths are found efficiently.

🔧 Debug

advanced

Identify the bug causing incorrect shortest path output

The following TypeScript code attempts to find shortest paths in a DAG but produces incorrect results. What is the bug?

DSA Typescript

function shortestPathBug(n: number, edges: [number, number, number][], src: number): number[] {
  const graph = new Map<number, [number, number][]>();
  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [u, v, w] of edges) {
    graph.get(u)!.push([v, w]);
  }

  const visited = new Array(n).fill(false);
  const stack: number[] = [];

  function dfs(node: number) {
    visited[node] = true;
    for (const [nbr] of graph.get(node)!) {
      if (!visited[nbr]) dfs(nbr);
    }
    stack.push(node);
  }

  for (let i = 0; i < n; i++) {
    if (!visited[i]) dfs(i);
  }

  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;

  while (stack.length) {
    const node = stack.pop()!;
    if (dist[node] !== Infinity) {
      for (const [nbr, w] of graph.get(node)!) {
        if (dist[node] + w < dist[nbr]) {
          dist[nbr] = dist[node] + w;
        }
      }
    }
  }

  return dist;
}

A Not marking nodes as visited before DFS causes infinite recursion.

B Not initializing dist[src] to 0 causes all distances to remain Infinity.

C Using stack.pop() instead of stack.shift() causes nodes to be processed in reverse order.

D Using stack.unshift(node) instead of stack.push(node) in DFS reverses topological order causing incorrect processing.

💡 Hint

Check how nodes are added to the stack during DFS and how that affects order.

Using stack.unshift(node) adds nodes to the front, reversing the intended topological order. The algorithm expects nodes in stack in reverse topological order to pop correctly. This causes incorrect distance updates.

📝 Syntax

advanced

Identify the syntax error in the shortest path code snippet

Which option contains a syntax error preventing the shortest path code from compiling?

DSA Typescript

const graph = new Map<number, [number, number][]>()
for (let i = 0; i < n; i++) {
  graph.set(i, [])
}
for (const [u, v, w] of edges) {
  graph.get(u)!.push([v, w])
}

const dist = new Array(n).fill(Infinity)
dist[src] = 0

while (stack.length) {
  const node = stack.pop()!
  if (dist[node] !== Infinity) {
    for (const [nbr, w] of graph.get(node)!) {
      if (dist[node] + w < dist[nbr]) {
        dist[nbr] = dist[node] + w
      }
    }
  }
}

A const dist = new Array(n).fill(Infinity) dist[src] = 0 // Missing semicolon between statements

B for (const [nbr, w] of graph.get(node)!) { if (dist[node] + w < dist[nbr]) { dist[nbr] = dist[node] + w } } // Correct syntax

C for (const [u, v, w] of edges) { graph.get(u)!.push([v, w]) } // Missing semicolon causes syntax error

D const node = stack.pop()! // The exclamation mark is invalid syntax in TypeScript

💡 Hint

Look for missing punctuation between statements.

In TypeScript, statements must be separated by semicolons or newlines. Option A misses a semicolon or newline between two statements, causing a syntax error.

🚀 Application

expert

Calculate number of nodes reachable with finite shortest path

After running shortest path in a DAG from source 0, how many nodes have a finite shortest distance (not Infinity) given the edges below?

DSA Typescript

const n = 7;
const edges: [number, number, number][] = [
  [0, 1, 2],
  [0, 2, 4],
  [1, 3, 7],
  [2, 4, 1],
  [4, 3, 2],
  [5, 6, 3]
];

// Run shortest path from source 0 using topological order
// Count nodes with dist[node] !== Infinity

A 5

B 6

C 4

D 7

💡 Hint

Nodes 5 and 6 are disconnected from source 0.

Nodes reachable from 0 are 0,1,2,3,4 with finite distances. Nodes 5 and 6 are disconnected, so their distances remain Infinity. Total reachable nodes with finite distance: 5.