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

Concept Flow - Shortest Path in DAG Using Topological Order

Build graph with edges and weights

↓

Find topological order

↓

Initialize distances (start=0, others=∞)

↓

For each node in topo order

↓

Relax edges from current node

↓

Update distances if shorter path found

↓

Done

↓

Shortest distances from start to all nodes

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

Execution Sample

DSA Typescript

const graph = new Map<number, [number, number][]>();
graph.set(0, [[1, 2], [2, 4]]);
graph.set(1, [[2, 1], [3, 7]]);
graph.set(2, [[4, 3]]);
graph.set(3, [[5, 1]]);
graph.set(4, [[3, 2], [5, 5]]);

// Find shortest paths from node 0

This code sets up a weighted directed graph and prepares to find shortest paths from node 0.

Execution Table

Step	Operation	Current Node	Distances Before	Edge Relaxed	Distances After	Visual State
1	Topological Sort	-	-	-	-	Topo order: [0,1,2,4,3,5]
2	Initialize distances	-	-	-	0:0,1:∞,2:∞,3:∞,4:∞,5:∞	Distances: [0,∞,∞,∞,∞,∞]
3	Relax edges from node 0	0	[0,∞,∞,∞,∞,∞]	0->1 (2)	[0,2,∞,∞,∞,∞]	Updated dist[1]=2
4	Relax edges from node 0	0	[0,2,∞,∞,∞,∞]	0->2 (4)	[0,2,4,∞,∞,∞]	Updated dist[2]=4
5	Relax edges from node 1	1	[0,2,4,∞,∞,∞]	1->2 (1)	[0,2,3,∞,∞,∞]	Updated dist[2]=3 (2+1)
6	Relax edges from node 1	1	[0,2,3,∞,∞,∞]	1->3 (7)	[0,2,3,9,∞,∞]	Updated dist[3]=9 (2+7)
7	Relax edges from node 2	2	[0,2,3,9,∞,∞]	2->4 (3)	[0,2,3,9,6,∞]	Updated dist[4]=6 (3+3)
8	Relax edges from node 4	4	[0,2,3,9,6,∞]	4->3 (2)	[0,2,3,8,6,∞]	Updated dist[3]=8 (6+2)
9	Relax edges from node 4	4	[0,2,3,8,6,∞]	4->5 (5)	[0,2,3,8,6,11]	Updated dist[5]=11 (6+5)
10	Relax edges from node 3	3	[0,2,3,8,6,11]	3->5 (1)	[0,2,3,8,6,9]	Updated dist[5]=9 (8+1)
11	Relax edges from node 5	5	[0,2,3,8,6,9]	-	[0,2,3,8,6,9]	No edges to relax
12	End	-	-	-	-	Final distances: [0,2,3,8,6,9]

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

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 10	Final
distances	[0,∞,∞,∞,∞,∞]	[0,2,∞,∞,∞,∞]	[0,2,3,9,∞,∞]	[0,2,3,9,6,∞]	[0,2,3,8,6,9]	[0,2,3,8,6,9]
current_node	-	0	1	2	3	5
topo_order	-	-	-	-	-	[0,1,2,4,3,5]

Key Moments - 3 Insights

Why do we relax edges in topological order?

Relaxing edges in topological order ensures that when we process a node, all shortest paths to it are already found, as shown in steps 3 to 10 in the execution_table.

Why do some distances update multiple times?

Distances update when a shorter path is found later in the order, like dist[2] updated at step 5 after step 4, because a better path was discovered.

Why is the initial distance to start node zero and others infinity?

Start node distance is zero because it's the source; others are infinity to represent unknown paths, as initialized in step 2.

Visual Quiz - 3 Questions

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

A 4

B ∞

C 3

D 2

💡 Hint

Check the 'Distances After' column at step 5 in execution_table.

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

A Step 10

B Step 9

C Step 8

D Step 11

💡 Hint

Look for the first 'Updated dist[5]' in the 'Visual State' column.

If the edge 4->3 had weight 10 instead of 2, how would the distance to node 3 change after step 8?

A It would remain 9

B It would become 16

C It would become 8

D It would become 6

💡 Hint

Check step 6 distance to node 3 and compare with step 8 update logic.

Concept Snapshot

Shortest Path in DAG Using Topological Order:
- Build graph with weighted edges
- Find topological order of nodes
- Initialize distances: start=0, others=∞
- Relax edges in topo order to update shortest distances
- Final distances give shortest path from start to all nodes

Full Transcript

We start by building a weighted directed graph. Then, we find a topological order of the nodes, which means an order where all edges go from earlier to later nodes. We initialize distances with zero for the start node and infinity for others. Then, we process each node in topological order, relaxing edges by checking if going through the current node offers a shorter path to neighbors. We update distances accordingly. This process ensures shortest paths are found efficiently in a DAG. The execution table shows each step with distances before and after relaxing edges, and the variable tracker shows how distances and current nodes change over time.

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