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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of shortest path distances in DAG

What is the output of the shortest path distances array after running the given code on the DAG with source vertex 0?

DSA Javascript

const graph = [
  [{to: 1, weight: 2}, {to: 2, weight: 4}],
  [{to: 2, weight: 1}, {to: 3, weight: 7}],
  [{to: 4, weight: 3}],
  [{to: 5, weight: 1}],
  [{to: 3, weight: 2}, {to: 5, weight: 5}],
  []
];

function topologicalSort(graph) {
  const visited = new Array(graph.length).fill(false);
  const stack = [];

  function dfs(node) {
    visited[node] = true;
    for (const edge of graph[node]) {
      if (!visited[edge.to]) dfs(edge.to);
    }
    stack.push(node);
  }

  for (let i = 0; i < graph.length; i++) {
    if (!visited[i]) dfs(i);
  }
  return stack.reverse();
}

function shortestPathDAG(graph, source) {
  const order = topologicalSort(graph);
  const dist = new Array(graph.length).fill(Infinity);
  dist[source] = 0;

  for (const u of order) {
    if (dist[u] !== Infinity) {
      for (const edge of graph[u]) {
        if (dist[edge.to] > dist[u] + edge.weight) {
          dist[edge.to] = dist[u] + edge.weight;
        }
      }
    }
  }
  return dist;
}

console.log(shortestPathDAG(graph, 0));

A [0, 2, 4, 7, 6, 8]

B [0, 2, 3, 9, 6, 8]

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

D [0, 2, 3, 7, 5, 8]

💡 Hint

Trace the topological order and update distances step-by-step.

The topological order is [0,1,2,4,3,5]. Starting from source 0 with distance 0, distances update as follows: 0->1=2, 0->2=4, then 1->2=3 (updated to 3 since 2+1=3 < 4), 1->3=9, 2->4=6, 4->3=8 (updated to 7 since 6+2=8 > 7), 4->5=11, 3->5=8 (updated to 8 since 7+1=8 < 11). Final distances: [0,2,3,7,6,8].

🧠 Conceptual

intermediate

Why topological order is used in shortest path for DAG?

Why do we use topological order to find the shortest path in a Directed Acyclic Graph (DAG)?

A Because it ensures we process each vertex only after all its predecessors, allowing correct distance updates without cycles.

B Because it sorts vertices by their weights to find the shortest path faster.

C Because it groups vertices by their degree to optimize traversal.

D Because it randomly orders vertices to avoid infinite loops.

💡 Hint

Think about how processing order affects distance updates in graphs without cycles.

Topological order processes vertices so that all edges go from earlier to later vertices. This guarantees that when we update distances for a vertex, all possible shorter paths from predecessors are already computed, avoiding revisits and cycles.

🔧 Debug

advanced

Identify the error in shortest path code for DAG

What error will occur when running this code snippet for shortest path in a DAG?

DSA Javascript

function shortestPathDAG(graph, source) {
  const order = topologicalSort(graph);
  const dist = new Array(graph.length).fill(Infinity);
  dist[source] = 0;

  for (const u of order) {
    for (const edge of graph[u]) {
      if (dist[edge.to] > dist[u] + edge.weight) {
        dist[edge.to] = dist[u] + edge.weight;
      }
    }
  }
  return dist;
}

// graph and topologicalSort defined correctly
console.log(shortestPathDAG(graph, 0));

A Incorrect distances because code does not check if dist[u] is Infinity before relaxing edges.

B TypeError because dist[u] might be Infinity and adding weight causes error.

C ReferenceError because topologicalSort is not defined.

D No error; code runs correctly and returns shortest distances.

💡 Hint

Check if the code verifies if the current distance is valid before updating neighbors.

The code does not check if dist[u] is Infinity before relaxing edges. This causes incorrect updates because adding weight to Infinity results in Infinity, but the comparison may incorrectly update distances.

❓ Predict Output

advanced

Output of shortest path distances with unreachable nodes

Given the graph below and source vertex 0, what is the output of the shortest path distances array?

DSA Javascript

const graph = [
  [{to: 1, weight: 3}],
  [{to: 2, weight: 4}],
  [],
  [{to: 4, weight: 2}],
  []
];

function topologicalSort(graph) {
  const visited = new Array(graph.length).fill(false);
  const stack = [];

  function dfs(node) {
    visited[node] = true;
    for (const edge of graph[node]) {
      if (!visited[edge.to]) dfs(edge.to);
    }
    stack.push(node);
  }

  for (let i = 0; i < graph.length; i++) {
    if (!visited[i]) dfs(i);
  }
  return stack.reverse();
}

function shortestPathDAG(graph, source) {
  const order = topologicalSort(graph);
  const dist = new Array(graph.length).fill(Infinity);
  dist[source] = 0;

  for (const u of order) {
    if (dist[u] !== Infinity) {
      for (const edge of graph[u]) {
        if (dist[edge.to] > dist[u] + edge.weight) {
          dist[edge.to] = dist[u] + edge.weight;
        }
      }
    }
  }
  return dist;
}

console.log(shortestPathDAG(graph, 0));

A [0, 3, Infinity, Infinity, Infinity]

B [0, 3, 7, 0, 2]

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

D [0, 3, 7, Infinity, Infinity]

💡 Hint

Nodes 3 and 4 are disconnected from source 0; their distances remain Infinity.

Nodes 3 and 4 are not reachable from source 0. Distances for unreachable nodes remain Infinity. Distances for reachable nodes 1 and 2 are updated correctly: 0->1=3, 1->2=7.

🧠 Conceptual

expert

Time complexity of shortest path in DAG using topological order

What is the time complexity of finding the shortest path in a DAG using topological order and edge relaxation?

A O(V^2), because each vertex is compared with all others

B O(V + E), where V is vertices and E is edges

C O(E log V), due to priority queue operations

D O(V!), because of permutations in topological sorting

💡 Hint

Consider the cost of topological sort and single pass edge relaxation.

Topological sort takes O(V + E). Relaxing edges once in topological order also takes O(E). Total time is O(V + E). No priority queue is used.

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