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

Concept Flow - Shortest Path in DAG Using Topological Order

Build graph with edges and weights

↓

Find topological order of nodes

↓

Initialize distances with infinity except start node

↓

For each node in topological order

↓

Relax edges from current node

↓

Update shortest distances

↓

End: shortest distances to all nodes found

We first get nodes in order so all edges go forward, then update shortest paths step-by-step.

Execution Sample

DSA Python

graph = {0: [(1, 2), (2, 4)], 1: [(2, 1), (3, 7)], 2: [(4, 3)], 3: [(5, 1)], 4: [(3, 2), (5, 5)], 5: []}
start = 0
# Find shortest paths from start using topological order

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

Execution Table

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

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

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 9	After Step 10	Final
distances	{0:∞,1:∞,2:∞,3:∞,4:∞,5:∞}	{0:0,1:∞,2:∞,3:∞,4:∞,5:∞}	{0:0,1:2,2:4,3:∞,4:∞,5:∞}	{0:0,1:2,2:3,3:9,4:∞,5:∞}	{0:0,1:2,2:3,3:8,4:6,5:11}	{0:0,1:2,2:3,3:8,4:6,5:9}	{0:0,1:2,2:3,3:8,4:6,5:9}
current_node	-	-	0	1	4	3	-

Key Moments - 3 Insights

Why do we process nodes in topological order?

Because in a DAG, topological order ensures all edges go from earlier to later nodes, so when relaxing edges, the shortest distances to previous nodes are already finalized (see execution_table step 1 and 3).

Why do we initialize distances with infinity except the start node?

Infinity means unknown or unreachable distance. Setting start node distance to 0 means we start there. This is shown in execution_table step 2 where distances are set before relaxation.

Why do some distances get updated multiple times?

Because a shorter path may be found later through different nodes. For example, distance to node 2 updates from 4 to 3 at step 5 (execution_table), showing relaxation improves distances.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the distance to node 2 after relaxation?

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 9

B Step 10

C Step 8

D Step 6

💡 Hint

Look for the first time 'Updated dist to 5' appears in the Visual State column.

If the edge 4->5 had weight 1 instead of 5, how would the final distance to node 5 change?

A It would be 5

B It would be 7

C It would be 9

D It would be 11

💡 Hint

Check distances after step 9 and step 10; changing edge weight affects relaxation results.

Concept Snapshot

Shortest Path in DAG Using Topological Order:
- Find topological order of nodes
- Initialize distances (start=0, others=∞)
- For each node in order, relax all outgoing edges
- Update distances if shorter path found
- Result: shortest distances from start to all nodes

Full Transcript

To find shortest paths in a Directed Acyclic Graph (DAG), we first get a topological order of nodes so all edges go forward. We initialize distances with infinity except the start node which is zero. Then, we process each node in topological order, relaxing edges to update shortest distances. Relaxing means checking if going through current node gives a shorter path to neighbors. We update distances accordingly. This process continues until all nodes are processed. The final distances represent shortest paths from the start node to every other node in the graph.

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

B. It guarantees the graph has cycles.

C. It sorts the graph by edge 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 vertices in a linear order without revisiting nodes. -> Option A

4. Quick Check:

   Topological order = linear processing [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 edge weights

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

easy

A. dist = [float('inf')] * 5; dist[5] = 0

B. dist = [0] * 5; dist[0] = float('inf')

C. dist = [None] * 5; dist[0] = 0

D. dist = [float('inf')] * 5; dist[0] = 0

Solution

1. Step 1: Initialize distances with infinity

   We set all distances to infinity to represent unknown paths initially.

2. Step 2: Set start node distance to zero

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

3. Final Answer:

   dist = [float('inf')] * 5; dist[0] = 0 -> Option D

4. Quick Check:

   Start node distance = 0, others = infinity [OK]

Hint: Start distance zero, others infinity for shortest path [OK]

Common Mistakes:

• Setting start node distance to infinity
• Using invalid index dist[5] (out of range)
• Initializing distances with zeros

3. Given the DAG edges with weights: 0->1 (2), 0->2 (4), 1->2 (1), 1->3 (7), 2->3 (3), and start node 0, what is the shortest distance to node 3 after running shortest path using topological order?

medium

A. 6

B. 7

C. 9

D. 10

Solution

1. Step 1: Calculate distances step-by-step

   Start dist: [0, inf, inf, inf]. 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[3]=min(9,3+3=6)=6.

2. Step 2: Final shortest distance to node 3

   The shortest distance to node 3 is 6 after updates.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest path to 3 = 6 [OK]

Hint: Update distances using topological order edges [OK]

Common Mistakes:

• Not updating dist[2] to 3 via node 1
• Taking longer path 0->1->3 as shortest
• Ignoring edge weights when updating distances

4. Consider this code snippet for shortest path in DAG:

dist = [float('inf')] * 4
dist[0] = 0
topo_order = [0, 1, 2, 3]
graph = {0: [(1, 1), (2, 4)], 1: [(2, 2), (3, 6)], 2: [(3, 3)], 3: []}
for u in topo_order:
    for v, w in graph[u]:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
print(dist)

What is the output?

medium

A. [0, 1, 2, 5]

B. [0, 1, 4, 7]

C. [0, 1, 3, 6]

D. [0, 1, 3, 9]

Solution

1. Step 1: Initialize distances and process node 0

   dist = [0, inf, inf, inf]. From 0: dist[1]=1, dist[2]=4.

2. Step 2: Process node 1 and update distances

   From 1: dist[2]=min(4,1+2=3)=3, dist[3]=1+6=7.

3. Step 3: Process node 2 and update distance

   From 2: dist[3]=min(7,3+3=6)=6.

4. Step 4: Final distances array

   dist = [0, 1, 3, 6]

5. Final Answer:

   [0, 1, 3, 6] -> Option C

6. Quick Check:

   Distances updated correctly using topological order [OK]

Hint: Update dist[v] only if new path is shorter [OK]

Common Mistakes:

• Not updating dist[2] to 3 via node 1
• Using wrong edge weights
• Printing dist before updates complete

5. You have a DAG with nodes 0 to 4 and edges: 0->1 (3), 0->2 (6), 1->2 (4), 1->3 (4), 2->3 (8), 3->4 (2). Using topological order [0,1,2,3,4], what is the shortest path distance from node 0 to node 4?

hard

A. 15

B. 9

C. 13

D. 11

Solution

1. Step 1: Initialize distances and update from node 0

   dist = [0, inf, inf, inf, inf]. From 0: dist[1]=3, dist[2]=6.

2. Step 2: Update distances from node 1 and 2

   From 1: dist[2]=min(6,3+4=7)=6 (unchanged), dist[3]=3+4=7. From 2: dist[3]=min(7,6+8=14)=7 (unchanged).

3. Step 3: Update distance from node 3 to 4

   dist[4]=7+2=9.

4. Step 4: Final shortest distance to node 4

   The shortest distance to node 4 is 9.

5. Final Answer:

   9 -> Option B

6. Quick Check:

   Shortest path 0->1->3->4 = 9 [OK]

Hint: Check all edges in topological order for shortest updates [OK]

Common Mistakes:

• Choosing longer path 0->2->3->4
• Adding weights incorrectly
• Ignoring topological order updates