Shortest Path in DAG Using Topological Order in DSA Javascript - 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 Javascript

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

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

A0

BInfinity

C-1

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 for all distances instead of Infinity

Using null which is not a number

Using -1 which can cause wrong comparisons

We use Infinity to represent initially unknown distances, except the source which is 0.

2fill in blank

medium

Complete the code to perform topological sorting using DFS.

DSA Javascript

function topoSortUtil(u, visited, stack) {
  visited[u] = true;
  for (const [v] of graph[u]) {
    if (!visited[v]) {
      topoSortUtil(v, visited, stack);
    }
  }
  stack.push([1]);
}

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

Avisited

Bstack

Cu

Dv

Attempts:

3 left

💡 Hint

Common Mistakes

Pushing neighbor v instead of current vertex u

Pushing the entire stack or visited array

We push the current vertex u onto the stack after visiting all its neighbors.

3fill in blank

hard

Fix the error in updating the distance of adjacent vertices in the shortest path calculation.

DSA Javascript

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

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

A<

B<=

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using greater than which updates with longer paths

Using less than or equal which can cause unnecessary updates

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

4fill in blank

hard

Fill both blanks to correctly iterate over vertices in topological order and update distances.

DSA Javascript

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

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

AInfinity

B0

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Checking distance against 0 instead of Infinity

Using greater than instead of less than in comparison

We skip vertices with infinite distance and update neighbors if new distance is less than current.

5fill in blank

hard

Fill all three blanks to create a dictionary of shortest distances for vertices reachable from source.

DSA Javascript

const shortestPaths = {
  [1]: dist[[2]] for [3] in [...Array(V).keys()] if dist[[3]] !== Infinity
};

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

Av

Bdist

Dk

Attempts:

3 left

💡 Hint

Common Mistakes

Using inconsistent variable names

Using keys instead of vertices in the comprehension

We map each vertex v to its distance dist[v] for all vertices v with finite distance.

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 allows processing nodes in a linear order without revisiting them.

B. It guarantees the graph has cycles.

C. It sorts nodes based on their weights.

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

Solution

1. Step 1: Understand topological order in DAG

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

2. Step 2: Use topological order for shortest path

   Processing nodes in this order means each node is visited once, and distances can be updated efficiently without revisiting.

3. Final Answer:

   It allows processing nodes in a linear order without revisiting them. -> Option A

4. Quick Check:

   Topological order = linear processing without revisits [OK]

Hint: Topological order processes nodes once for shortest path [OK]

Common Mistakes:

• Thinking topological order sorts by weights
• Assuming DAG has cycles
• Confusing shortest path with longest path

2. Which of the following JavaScript code snippets correctly initializes the distance array for shortest path calculation in a DAG with 5 nodes, starting from node 0?

easy

A. const dist = Array(5).fill(-1); dist[0] = 0;

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

C. const dist = Array(5).fill(null); dist[0] = 0;

D. const dist = Array(5).fill(Infinity); dist[0] = 0;

Solution

1. Step 1: Initialize distances for shortest path

   Distances to all nodes except start should be Infinity to represent unknown paths.

2. Step 2: Set start node distance to zero

   Distance to start node (0) is zero because it is the source.

3. Final Answer:

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

4. Quick Check:

   Start distance 0, others Infinity [OK]

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

Common Mistakes:

• Setting start node distance to Infinity
• Using 0 for all distances initially
• Using null or -1 which are invalid for distances

3. Consider the following DAG represented as adjacency list with weights:

const graph = {
  0: [[1, 2], [2, 4]],
  1: [[2, 1], [3, 7]],
  2: [[4, 3]],
  3: [[4, 1]],
  4: []
};

If we run shortest path from node 0 using topological order, what is the shortest distance to node 4?

medium

A. 6

B. 7

C. 10

D. 9

Solution

1. Step 1: Find topological order and initialize distances

   Topological order could be [0,1,2,3,4]. Initialize dist = [0, Infinity, Infinity, Infinity, Infinity].

2. Step 2: Relax edges in topological order

   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.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest distance to node 4 = 6 [OK]

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

Common Mistakes:

• Not updating dist[2] to smaller value 3
• Ignoring edge from 3 to 4
• Adding weights incorrectly

4. The following code attempts to find the shortest path in a DAG using topological order but has a bug:

function shortestPath(graph, start) {
  const dist = Array(Object.keys(graph).length).fill(Infinity);
  dist[start] = 0;
  const topoOrder = topologicalSort(graph);
  for (const node of topoOrder) {
    for (const [neighbor, weight] of graph[node]) {
      if (dist[node] + weight < dist[neighbor]) {
        dist[neighbor] = dist[node] + weight;
      }
    }
  }
  return dist;
}

What is the likely cause of incorrect results?

medium

A. The start node distance is not set to zero

B. dist array is initialized with zeros instead of Infinity

C. topologicalSort function might return nodes in wrong order

D. The graph edges are not weighted

Solution

1. Step 1: Check initialization and start distance

   dist is correctly initialized with Infinity and start node distance set to 0.

2. Step 2: Verify topological order correctness

   If topologicalSort returns nodes in wrong order, relaxation will fail and distances won't update correctly.

3. Final Answer:

   topologicalSort function might return nodes in wrong order -> Option C

4. Quick Check:

   Correct topological order needed for shortest path [OK]

Hint: Ensure topological order is correct before relaxing edges [OK]

Common Mistakes:

• Assuming dist initialization is wrong
• Ignoring importance of topological order
• Forgetting to set start node distance

5. Given a DAG with nodes 0 to 5 and edges with weights:

0 -> 1 (3), 0 -> 2 (2), 1 -> 3 (4), 2 -> 3 (1), 3 -> 4 (2), 4 -> 5 (1)

If you want to find the shortest path from node 0 to node 5 using topological order, which sequence of distances will you get before processing node 3?

hard

A. [0, 3, 2, 5, Infinity, Infinity]

B. [0, 3, 2, 3, Infinity, Infinity]

C. [0, 3, 2, 3, 2, Infinity]

D. [0, 3, 2, 1, Infinity, Infinity]

Solution

1. Step 1: Initialize distances and process nodes 0,1,2

   Start dist = [0, Infinity, Infinity, Infinity, Infinity, Infinity]. After 0: dist[1]=3, dist[2]=2. After 1: dist[3]=3+4=7. After 2: dist[3]=min(7,2+1=3)=3.

2. Step 2: Before processing node 3

   At this point, node 3's distance has been finalized by its predecessors to 3, but outgoing edges from 3 have not been relaxed yet, so dist[4] and dist[5] remain Infinity. Distances: [0, 3, 2, 3, Infinity, Infinity].

3. Final Answer:

   [0, 3, 2, 3, Infinity, Infinity] -> Option B

4. Quick Check:

   Distances before relaxing node 3 edges [OK]

Hint: Check distances before relaxing edges from current node [OK]

Common Mistakes:

• Updating distances of neighbors too early
• Confusing order of relaxation
• Miscomputing minimum distances