Shortest Path in DAG Using Topological Order in DSA C++ - 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=inf)

↓

For each node in topo order

↓

Relax edges from current node

↓

Update distances if shorter path found

↓

Repeat for all nodes

↓

Final shortest distances from start node

We first build the graph and find a topological order. Then we initialize distances and relax edges in that order to find shortest paths.

Execution Sample

DSA C++

1. Build graph with edges and weights
2. Find topological order
3. Initialize distances: dist[start]=0, others=inf
4. For each node in topo order:
     For each edge (node->neighbor):
         if dist[node]+weight < dist[neighbor]:
             dist[neighbor] = dist[node]+weight

This code finds shortest paths from a start node in a DAG by relaxing edges in topological order.

Execution Table

Step	Operation	Current Node	Edge Relaxed	Distance Update	Distances State	Visual State
1	Build graph	-	-	-	-	Graph with edges and weights created
2	Find topo order	-	-	-	-	Topological order found: [0, 1, 2, 3, 4]
3	Initialize distances	-	-	-	dist = [0, ∞, ∞, ∞, ∞]	Start node distance set to 0
4	Relax edges from node 0	0	0->1 (weight 3)	dist[1] = 0+3=3	dist = [0, 3, ∞, ∞, ∞]	Edge relaxed, dist updated
5	Relax edges from node 0	0	0->2 (weight 6)	dist[2] = 0+6=6	dist = [0, 3, 6, ∞, ∞]	Edge relaxed, dist updated
6	Relax edges from node 1	1	1->2 (weight 4)	dist[2] = min(6, 3+4=7)=6 (no update)	dist = [0, 3, 6, ∞, ∞]	No update, shorter path not found
7	Relax edges from node 1	1	1->3 (weight 4)	dist[3] = 3+4=7	dist = [0, 3, 6, 7, ∞]	Edge relaxed, dist updated
8	Relax edges from node 2	2	2->4 (weight 2)	dist[4] = 6+2=8	dist = [0, 3, 6, 7, 8]	Edge relaxed, dist updated
9	Relax edges from node 3	3	3->4 (weight 1)	dist[4] = min(8, 7+1=8)=8 (no update)	dist = [0, 3, 6, 7, 8]	No update, equal path found
10	Relax edges from node 4	4	-	No edges	dist = [0, 3, 6, 7, 8]	No edges to relax
11	End	-	-	-	Final distances: [0, 3, 6, 7, 8]	Shortest paths found

💡 All nodes processed in topological order; no more edges to relax.

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
dist[0]	0	0	0	0	0	0	0	0
dist[1]	∞	3	3	3	3	3	3	3
dist[2]	∞	∞	6	6	6	6	6	6
dist[3]	∞	∞	∞	∞	7	7	7	7
dist[4]	∞	∞	∞	∞	∞	8	8	8

Key Moments - 3 Insights

Why do we process nodes in topological order?

Processing nodes in topological order ensures all edges from earlier nodes are relaxed before their neighbors, so distances are updated correctly without revisiting nodes. See execution_table steps 4-10.

Why don't we update dist[2] at step 6 when 3+4=7 is greater than current 6?

We only update if the new distance is smaller. Since 7 > 6, no update happens. This prevents longer paths from overwriting shorter ones. See execution_table step 6.

What if the graph had cycles?

Topological order only exists for DAGs (no cycles). If cycles exist, this method fails because no valid topological order can be found.

Visual Quiz - 3 Questions

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

A 6

B 7

C ∞

D 3

💡 Hint

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

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

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

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

If the edge 1->2 had weight 1 instead of 4, what would happen at step 6?

A dist[2] would update to 3

B dist[2] would remain 6

C dist[2] would update to 4

D dist[2] would update to 7

💡 Hint

Calculate dist[1] + new weight and compare with current dist[2] at step 6.

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 topological order
- Update distances if shorter path found
- Final distances give shortest paths from start

Full Transcript

This concept finds shortest paths in a Directed Acyclic Graph (DAG) using topological order. First, the graph is built with edges and weights. Then, a topological order of nodes is found, which means nodes are arranged so all edges go from earlier to later nodes. Distances are initialized with the start node at zero and others at infinity. We then process each node in topological order, relaxing edges by checking if going through the current node offers a shorter path to neighbors. If yes, distances are updated. This process continues until all nodes are processed, resulting in shortest distances from the start node to all others. The execution table shows each step, the node processed, edges relaxed, and distance updates. Key moments clarify why topological order is needed and why updates happen only when shorter paths are found. The visual quiz tests understanding of distance updates and the effect of edge weights.

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 no cycles.

C. It finds the longest path instead of the shortest path.

D. It works only for undirected graphs.

Solution

1. Step 1: Understand topological order in DAG

   Topological order arranges vertices so that all edges go from earlier to later vertices, allowing linear processing.

2. Step 2: Use topological order for shortest path

   Processing vertices in this order ensures each vertex is relaxed once, avoiding revisits and cycles.

3. Final Answer:

   It allows processing vertices in a linear order without revisiting nodes. -> Option A

4. Quick Check:

   Topological order = linear processing without revisits [OK]

Hint: Topological order processes nodes once in DAG [OK]

Common Mistakes:

• Thinking it works for graphs with cycles
• Confusing shortest path with longest path
• Assuming it works for undirected graphs

2. Which of the following C++ code snippets correctly initializes the distance array for shortest path calculation in a DAG with n vertices, assuming source vertex is 0?

easy

A. std::vector<int> dist(n, 0); dist[0] = INT_MAX;

B. std::vector<int> dist(n, INT_MAX); dist[0] = 0;

C. int dist[n]; for(int i=0; i

D. std::vector<int> dist(n); dist[0] = 0;

Solution

1. Step 1: Initialize distances with maximum value

   Distances should start as infinity (INT_MAX) except source which is 0.

2. Step 2: Check code correctness

   std::vector<int> dist(n, INT_MAX); dist[0] = 0; correctly sets all distances to INT_MAX and source distance to 0.

3. Final Answer:

   std::vector<int> dist(n, INT_MAX); dist[0] = 0; -> Option B

4. Quick Check:

   Distance init = INT_MAX except source 0 [OK]

Hint: Initialize all distances to INT_MAX except source 0 [OK]

Common Mistakes:

• Setting source distance to INT_MAX
• Initializing distances to zero
• Not using vector or uninitialized array

3. Consider the following DAG with edges and weights:
0 -> 1 (2), 0 -> 2 (4), 1 -> 2 (1), 1 -> 3 (7), 2 -> 3 (3)
Using topological order starting from vertex 0, what is the shortest distance to vertex 3?

medium

A. 6

B. 7

C. 9

D. 10

Solution

1. Step 1: Find topological order and initialize distances

   Topological order: 0, 1, 2, 3. Initialize dist[0]=0, others = 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[3]=min(9, 3+3=6)=6

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest path to 3 = 6 [OK]

Hint: Relax edges in topological order to update shortest distances [OK]

Common Mistakes:

• Not updating dist[2] to 3 via vertex 1
• Ignoring relaxation from vertex 2 to 3
• Using wrong topological order

4. The following code snippet attempts to find shortest paths in a DAG but produces incorrect results. What is the bug?

std::vector<int> dist(n, INT_MAX);
dist[source] = 0;
for (int u : topoOrder) {
  for (auto &edge : graph[u]) {
    int v = edge.first, w = edge.second;
    if (dist[v] > dist[u] + w) {
      dist[v] = dist[u] + w;
    }
  }
}

medium

A. The distance array is not initialized properly.

B. The graph edges are not relaxed in topological order.

C. The source vertex distance is not set to zero.

D. The code does not check if dist[u] is INT_MAX before adding w.

Solution

1. Step 1: Analyze relaxation condition

   The code adds w to dist[u] without checking if dist[u] is INT_MAX, causing overflow.

2. Step 2: Identify missing check

   Before relaxing edges, must check dist[u] != INT_MAX to avoid invalid addition.

3. Final Answer:

   The code does not check if dist[u] is INT_MAX before adding w. -> Option D

4. Quick Check:

   Check dist[u] != INT_MAX before relaxation [OK]

Hint: Always check dist[u] != INT_MAX before adding edge weight [OK]

Common Mistakes:

• Assuming initialization is wrong
• Thinking topological order is incorrect
• Forgetting to set source distance

5. Given a DAG with vertices 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, what is the shortest path distance from vertex 0 to vertex 4?

hard

A. 13

B. 11

C. 9

D. 14

Solution

1. Step 1: Determine topological order and initialize distances

   Topological order: 0,1,2,3,4. Initialize dist[0]=0, others = infinity.

2. Step 2: Relax edges in order

   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[3]=min(7,6+8=14)=7
   From 3: dist[4]=7+2=9

3. Final Answer:

   9 -> Option C

4. Quick Check:

   Shortest path to 4 = 9 [OK]

Hint: Relax edges stepwise in topological order to find shortest path [OK]

Common Mistakes:

• Not updating dist[3] correctly
• Choosing longer path via vertex 2
• Misordering topological sort