Shortest Path in DAG Using Topological Order in DSA Javascript - Execution Trace

Concept Flow - Shortest Path in DAG Using Topological Order

Build graph with edges and weights

↓

Find topological order

↓

Initialize distances array with Infinity

↓

Set distance to source as 0

↓

For each node in topological order

↓

Relax edges from current node

↓

Update distances if shorter path found

↓

Repeat until all nodes processed

↓

Distances array holds shortest paths from source

We first build the graph, find a topological order, then relax edges in that order to find shortest paths.

Execution Sample

DSA Javascript

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

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

  const visited = new Set();
  const stack = [];

  function topologicalSort(node) {
    visited.add(node);
    if (graph[node]) {
      for (const [neighbor] of graph[node]) {
        if (!visited.has(neighbor)) {
          topologicalSort(neighbor);
        }
      }
    }
    stack.push(node);
  }

  for (const node in graph) {
    if (!visited.has(Number(node))) {
      topologicalSort(Number(node));
    }
  }

  while (stack.length) {
    const node = stack.pop();
    if (dist[node] !== Infinity) {
      for (const [neighbor, weight] of graph[node]) {
        if (dist[neighbor] > dist[node] + weight) {
          dist[neighbor] = dist[node] + weight;
        }
      }
    }
  }

  return dist;
}

const dist = shortestPathDAG(graph, 0);

This code finds shortest paths from node 0 in a weighted DAG using topological order.

Execution Table

Step	Operation	Current Node	Distances Array	Relaxed Edge	Distance Update	Visual State
1	Initialize distances	N/A	[0, ∞, ∞, ∞, ∞, ∞]	N/A	Set dist[0] = 0	0:0,1:∞,2:∞,3:∞,4:∞,5:∞
2	Process node 0	0	[0, ∞, ∞, ∞, ∞, ∞]	Edge 0->1 (weight 2)	dist[1] = 2	0:0,1:2,2:∞,3:∞,4:∞,5:∞
3	Process node 0	0	[0, 2, ∞, ∞, ∞, ∞]	Edge 0->2 (weight 4)	dist[2] = 4	0:0,1:2,2:4,3:∞,4:∞,5:∞
4	Process node 1	1	[0, 2, 4, ∞, ∞, ∞]	Edge 1->2 (weight 1)	dist[2] = 3 (updated)	0:0,1:2,2:3,3:∞,4:∞,5:∞
5	Process node 1	1	[0, 2, 3, ∞, ∞, ∞]	Edge 1->3 (weight 7)	dist[3] = 9	0:0,1:2,2:3,3:9,4:∞,5:∞
6	Process node 2	2	[0, 2, 3, 9, ∞, ∞]	Edge 2->4 (weight 3)	dist[4] = 6	0:0,1:2,2:3,3:9,4:6,5:∞
7	Process node 4	4	[0, 2, 3, 9, 6, ∞]	Edge 4->3 (weight 2)	dist[3] = 8 (updated)	0:0,1:2,2:3,3:8,4:6,5:∞
8	Process node 4	4	[0, 2, 3, 8, 6, ∞]	Edge 4->5 (weight 5)	dist[5] = 11	0:0,1:2,2:3,3:8,4:6,5:11
9	Process node 3	3	[0, 2, 3, 8, 6, 11]	Edge 3->5 (weight 1)	dist[5] = 9 (updated)	0:0,1:2,2:3,3:8,4:6,5:9
10	Process node 5	5	[0, 2, 3, 8, 6, 9]	No edges	No update	0:0,1:2,2:3,3:8,4:6,5:9
11	End	N/A	[0, 2, 3, 8, 6, 9]	N/A	All nodes processed	Final distances

💡 All nodes processed in topological order, shortest distances finalized.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	Final
dist	[∞, ∞, ∞, ∞, ∞, ∞]	[0, 2, ∞, ∞, ∞, ∞]	[0, 2, 3, 9, ∞, ∞]	[0, 2, 3, 9, 6, ∞]	[0, 2, 3, 8, 6, 11]	[0, 2, 3, 8, 6, 9]	[0, 2, 3, 8, 6, 9]
currentNode	N/A	0	1	2	4	5	N/A

Key Moments - 3 Insights

Why do we initialize all distances to Infinity except the source?

Because initially, we don't know any path to other nodes, so we set them as unreachable (Infinity). The source distance is zero since it's the start. See Step 1 in execution_table.

Why do we process nodes in topological order?

Processing in topological order ensures that when we relax edges from a node, all shortest paths to that node are already computed. This avoids revisiting nodes multiple times. See the order of currentNode in variable_tracker.

Why do distances get updated multiple times for some nodes?

Because a shorter path might be found later via a different route. For example, dist[2] updates from ∞ to 4, then to 3 at Step 4. This is shown in execution_table rows 3 and 4.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the distance to node 2 after relaxing edge 1->2?

A 3

B 4

C ∞

D 2

💡 Hint

Check the 'Distance Update' and 'Distances Array' columns at Step 4.

At which step does the distance to node 5 first get updated?

A Step 7

B Step 8

C Step 9

D Step 6

💡 Hint

Look for the first 'dist[5]' update in the 'Distance Update' column.

If the edge 4->5 had weight 1 instead of 5, what would be the distance to node 5 after Step 8?

A 6

B 11

C 7

D 9

💡 Hint

Add the new weight 1 to dist[4] which is 6 at Step 8.

Concept Snapshot

Shortest Path in DAG using Topological Order:
- Build graph with weighted edges
- Find topological order of nodes
- Initialize distances with Infinity, source = 0
- Process nodes in topological order
- Relax edges: update distances if shorter path found
- Result: distances array with shortest paths from source

Full Transcript

To find the shortest path in a Directed Acyclic Graph (DAG), we first build the graph with weighted edges. Then, we find a topological order of the nodes, which means an order where all edges go from earlier to later nodes. We initialize a distances array with Infinity for all nodes except the source node, which is set to zero. We then process each node in the topological order, relaxing edges by checking if going through the current node offers a shorter path to its neighbors. If yes, we update the distances. This process continues until all nodes are processed. The final distances array holds the shortest distances from the source to every other node. This method is efficient because it leverages the acyclic nature of the graph and processes nodes only once in order.

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