Shortest Path in DAG Using Topological Order in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance array with Infinity for all vertices except the source.

DSA Typescript

const dist: number[] = new Array(V).fill([1]);
dist[src] = 0;

Drag options to blanks, or click blank then click option'

A-1

B0

CInfinity

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 for all distances which incorrectly assumes all nodes are reachable immediately.

Using null which is not a number and will cause errors in calculations.

We use Infinity to represent that initially all vertices are unreachable except the source which is set to 0.

2fill in blank

medium

Complete the code to perform the topological sort using DFS.

DSA Typescript

function topoSort(u: number, visited: boolean[], stack: number[], graph: Array<Array<[number, number]>>): void {
  visited[u] = true;
  for (const [v, w] of graph[u]) {
    if (!visited[[1]]) {
      topoSort(v, visited, stack, graph);
    }
  }
  stack.push(u);
}

Drag options to blanks, or click blank then click option'

Av

Bw

Cstack

Du

Attempts:

3 left

💡 Hint

Common Mistakes

Checking the current vertex u instead of the neighbor v.

Using the weight w as a visited index which is incorrect.

We check if the adjacent vertex v is visited before calling DFS recursively.

3fill in blank

hard

Fix the error in the relaxation step inside the shortest path calculation.

DSA Typescript

for (const [v, w] of graph[u]) {
  if (dist[u] !== Infinity && dist[u] + w [1] dist[v]) {
    dist[v] = dist[u] + w;
  }
}

Drag options to blanks, or click blank then click option'

A>=

B>

C<=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using greater than operator which would update distances incorrectly.

Using less than or equal which can cause unnecessary updates.

We update the distance if the new path is shorter, so we check if dist[u] + w < dist[v].

4fill in blank

hard

Fill both blanks to complete the loop that processes vertices in topological order and relaxes edges.

DSA Typescript

while (stack.length > 0) {
  const u = stack.pop()!;
  if (dist[u] !== [1]) {
    for (const [v, w] of graph[u]) {
      if (dist[u] + w [2] dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }
}

Drag options to blanks, or click blank then click option'

AInfinity

B0

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for 0 instead of Infinity which skips valid vertices.

Using greater than operator which breaks shortest path logic.

The distance must not be Infinity to relax edges, and relaxation happens if the new distance is less than the current.

5fill in blank

hard

Fill all three blanks to complete the function that returns shortest distances from source in a DAG.

DSA Typescript

function shortestPathDAG(V: number, graph: Array<Array<[number, number]>>, src: number): number[] {
  const dist: number[] = new Array(V).fill([1]);
  dist[src] = 0;
  const visited: boolean[] = new Array(V).fill(false);
  const stack: number[] = [];
  for (let i = 0; i < V; i++) {
    if (!visited[i]) {
      [2](i, visited, stack, graph);
    }
  }
  while (stack.length > 0) {
    const u = stack.pop()!;
    if (dist[u] !== Infinity) {
      for (const [v, w] of graph[u]) {
        if (dist[u] + w [3] dist[v]) {
          dist[v] = dist[u] + w;
        }
      }
    }
  }
  return dist;
}

Drag options to blanks, or click blank then click option'

AInfinity

BtopoSort

C<

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Not initializing distances properly.

Calling wrong function or variable for topological sort.

Using wrong comparison operator in relaxation.

Initialize distances with Infinity, call topoSort for unvisited vertices, and relax edges when the new distance is less than the current.

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