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.

Practice

1. What is the main advantage of using topological order to find the shortest path in a Directed Acyclic Graph (DAG)?

easy

A. It finds the longest path instead of the shortest.

B. It guarantees the graph has cycles.

C. It allows processing vertices in a linear order without revisiting nodes.

D. It sorts vertices based on their weights.

Solution

1. Step 1: Understand topological order in DAG

   Topological order arranges vertices so that all edges go from earlier to later vertices, ensuring no cycles.

2. Step 2: Use topological order for shortest path

   Processing vertices in this order means each vertex is processed after all its predecessors, so shortest paths can be updated without revisiting.

3. Final Answer:

   It allows processing vertices in a linear order without revisiting nodes. -> Option C

4. Quick Check:

   Topological order = linear processing without revisits [OK]

Hint: Topological order processes nodes once in DAG [OK]

Common Mistakes:

• Thinking topological order applies to graphs with cycles
• Confusing shortest path with longest path
• Assuming topological order sorts by weights

2. Which TypeScript code snippet correctly initializes the distance array for shortest path calculation in a DAG with 5 vertices?

easy

A. const dist: number[] = Array(5).fill(Infinity); dist[0] = 0;

B. const dist: number[] = new Array(5).fill(0); dist[0] = Infinity;

C. const dist: number[] = Array(5).fill(-1); dist[0] = 0;

D. const dist: number[] = new Array(5).fill(null); dist[0] = 0;

Solution

1. Step 1: Initialize distances with Infinity except source

   Distances start as Infinity to represent unknown paths; source vertex distance is 0.

2. Step 2: Check code correctness

   const dist: number[] = Array(5).fill(Infinity); dist[0] = 0; uses Array(5).fill(Infinity) and sets dist[0] = 0, which is correct initialization.

3. Final Answer:

   const dist: number[] = Array(5).fill(Infinity); dist[0] = 0; -> Option A

4. Quick Check:

   Distance array initialized with Infinity except source 0 [OK]

Hint: Use Infinity for unknown distances, zero for source [OK]

Common Mistakes:

• Filling distances with 0 instead of Infinity
• Setting source distance to Infinity
• Using null or -1 which are invalid for distances

3. Given the following DAG edges with weights:
edges = [[0,1,2],[0,2,4],[1,2,1],[1,3,7],[2,4,3],[3,4,1]]
and source vertex 0, what is the shortest distance array after running shortest path using topological order?

medium

A. [0, 4, 5, 8, 9]

B. [0, 2, 4, 7, 8]

C. [0, 2, 3, 7, 6]

D. [0, 2, 3, 9, 6]

Solution

1. Step 1: Calculate shortest distances step-by-step

   Start dist = [0,∞,∞,∞,∞]. From 0: dist[1]=2, dist[2]=4. From 1: dist[2]=min(4,2+1=3)=3, dist[3]=2+7=9. From 2: dist[4]=3+3=6. From 3: dist[4]=min(6,9+1=10)=6.

2. Step 2: Final shortest distances

   Distances are [0, 2, 3, 9, 6]. But check [0, 2, 3, 7, 6] has dist[3]=7, so re-check: From 1 to 3 is 7, so dist[3]=2+7=9. [0, 2, 3, 7, 6] shows 7, so [0, 2, 3, 9, 6] matches 9 for dist[3]. So [0, 2, 3, 9, 6] is correct.

3. Final Answer:

   [0, 2, 3, 9, 6] -> Option D

4. Quick Check:

   Shortest distances = [0, 2, 3, 9, 6] [OK]

Hint: Relax edges in topological order to update distances [OK]

Common Mistakes:

• Not updating distances with minimum values
• Mixing up edge weights during relaxation
• Ignoring topological order in updates

4. Identify the bug in this TypeScript code snippet for shortest path in DAG:

const dist = Array(n).fill(Infinity);
dist[0] = 0;
for (const u of topoOrder) {
  for (const [v, w] of graph[u]) {
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}

Assuming graph is adjacency list and topoOrder is correct topological order.

medium

A. No bug; the code correctly updates shortest distances.

B. The inner loop should iterate over graph[v] instead of graph[u].

C. dist[u] should be checked for Infinity before relaxation.

D. dist array should be initialized with zeros instead of Infinity.

Solution

1. Step 1: Analyze the relaxation in topological order

   In topological order, when processing u, dist[u] has been finalized as the shortest path from source if reachable. For unreachable u, dist[u] remains Infinity.

2. Step 2: Verify Infinity handling

   In JavaScript/TypeScript, Infinity + w = Infinity for any finite w, and Infinity < dist[v] is false, so no incorrect updates occur. Thus, no explicit check is needed.

3. Final Answer:

   No bug; the code correctly updates shortest distances. -> Option A

4. Quick Check:

   Infinity + w doesn't update distances wrongly [OK]

Hint: Infinity arithmetic handles unreachable nodes [OK]

Common Mistakes:

• Thinking explicit Infinity check is required
• Iterating over wrong adjacency list
• Initializing dist with zeros

5. You have a DAG with vertices 0 to 5 and edges:
[[0,1,3],[0,2,6],[1,2,4],[1,3,4],[2,4,8],[3,4,2],[4,5,1]]
Using shortest path with topological order from source 0, what is the shortest distance to vertex 5?

hard

A. 12

B. 10

C. 11

D. 9

Solution

1. Step 1: Initialize distances and process edges

   Start dist = [0,∞,∞,∞,∞,∞]. From 0: dist[1]=3, dist[2]=6. From 1: dist[2]=min(6,3+4=7)=6, dist[3]=3+4=7. From 2: dist[4]=6+8=14. From 3: dist[4]=min(14,7+2=9)=9. From 4: dist[5]=9+1=10.

2. Step 2: Verify shortest distance to vertex 5

   Shortest distance to 5 is 10, but check if any shorter path exists: 0->1->3->4->5 = 3+4+2+1=10, 0->2->4->5=6+8+1=15. So 10 is shortest.

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Shortest distance to 5 = 10 [OK]

Hint: Relax edges in topological order to find shortest path [OK]

Common Mistakes:

• Choosing longer path distances
• Ignoring better paths through intermediate vertices
• Miscomputing sums of edge weights