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.