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 of nodes

↓

Initialize distances: start node=0, others=∞

↓

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 start

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#

int[] dist = new int[V];
for (int i = 0; i < V; i++) dist[i] = int.MaxValue;
dist[start] = 0;
foreach (int u in topoOrder) {
  foreach (var (v, w) in graph[u]) {
    if (dist[u] != int.MaxValue && dist[u] + w < dist[v])
      dist[v] = dist[u] + w;
  }
}

This code initializes distances and relaxes edges in topological order to find shortest paths in a DAG.

Execution Table

Step	Operation	Current Node	Edge Relaxed	Distance Update	Distances Array	Visual State
1	Initialize distances	N/A	N/A	dist[0]=0, others=∞	[0, ∞, ∞, ∞, ∞]	Start node distance set to 0
2	Process node 0	0	(0->1, 3)	dist[1]=0+3=3	[0, 3, ∞, ∞, ∞]	Relax edge 0->1
3	Process node 0	0	(0->2, 6)	dist[2]=0+6=6	[0, 3, 6, ∞, ∞]	Relax edge 0->2
4	Process node 1	1	(1->2, 4)	dist[2]=min(6,3+4=7)=6	[0, 3, 6, ∞, ∞]	No update, 6 < 7
5	Process node 1	1	(1->3, 4)	dist[3]=3+4=7	[0, 3, 6, 7, ∞]	Relax edge 1->3
6	Process node 2	2	(2->4, 2)	dist[4]=6+2=8	[0, 3, 6, 7, 8]	Relax edge 2->4
7	Process node 3	3	(3->4, 1)	dist[4]=min(8,7+1=8)=8	[0, 3, 6, 7, 8]	No update, equal distances
8	Process node 4	4	No outgoing edges	No update	[0, 3, 6, 7, 8]	End of graph
9	Finish	N/A	N/A	All nodes processed	[0, 3, 6, 7, 8]	Shortest distances finalized

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 6	Final
dist	[∞, ∞, ∞, ∞, ∞]	[0, 3, ∞, ∞, ∞]	[0, 3, 6, ∞, ∞]	[0, 3, 6, 7, ∞]	[0, 3, 6, 7, 8]	[0, 3, 6, 7, 8]
current node	N/A	0	0	1	2	4

Key Moments - 3 Insights

Why do we initialize all distances to infinity except the start node?

Because initially we don't know any path to other nodes, so we set them to a very large number (infinity). The start node distance is zero since it's the starting point. See execution_table step 1.

Why do we process nodes in topological order?

Topological order ensures that when we process a node, all nodes that can reach it have already been processed. This guarantees correct relaxation of edges. See execution_table steps 2-8.

Why do some edge relaxations not update distances?

If the new calculated distance is not smaller than the current distance, we do not update. For example, step 4 shows no update because 6 < 7. This prevents incorrect longer paths.

Visual Quiz - 3 Questions

Look at the execution_table, what is the distance to node 3 after processing node 1?

A 7

B ∞

C 3

D 6

💡 Hint

Check the Distances Array column at step 5 in execution_table.

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

A Step 4

B Step 6

C Step 3

D Step 7

💡 Hint

Look for the first Distance Update to dist[4] in execution_table.

If the edge (1->2) had weight 1 instead of 4, how would the distance to node 2 change after step 4?

A It would become 7

B It would remain 6

C It would become 4

D It would become 3

💡 Hint

Check how dist[2] is updated in step 4 and recalculate with new weight.

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
- Result: shortest distances from start node

Full Transcript

To find the shortest path in a Directed Acyclic Graph (DAG), we first build the graph with weighted edges. We then find a topological order of the nodes, which means an order where every edge goes from an earlier node to a later node. We initialize distances with the start node distance as zero and all others as infinity, meaning unknown. Then, we process each node in topological order, relaxing edges by checking if going through the current node offers a shorter path to connected nodes. If yes, we update the distance. We repeat this until all nodes are processed. The final distances array holds the shortest path distances from the start node to every other node.

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 sorts edges by weight.

B. It guarantees the graph has cycles.

C. It allows processing vertices in a linear order without revisiting nodes.

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

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 allows updating shortest distances without revisiting nodes, making the algorithm efficient.

3. Final Answer:

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

4. Quick Check:

   Topological order = linear processing [OK]

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

Common Mistakes:

• Thinking topological order works with cycles
• Confusing shortest path with longest path
• Assuming edges are sorted by weight

2. Which of the following C# code snippets correctly initializes the distance array for shortest path calculation in a DAG with 5 vertices?

easy

A. int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = int.MaxValue;

B. int[] dist = new int[5] {0, 0, 0, 0, 0};

C. int[] dist = new int[5]; dist.Fill(int.MaxValue);

D. int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = 0;

Solution

1. Step 1: Understand distance initialization

   Distances should start as infinity (int.MaxValue) except the source, to represent unknown paths.

2. Step 2: Check code correctness

   int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = int.MaxValue; correctly sets all distances to int.MaxValue using a loop. int[] dist = new int[5] {0, 0, 0, 0, 0}; sets all to zero, which is incorrect. int[] dist = new int[5]; dist.Fill(int.MaxValue); uses a non-existent Fill method. int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = 0; sets all to zero, which is wrong.

3. Final Answer:

   int[] dist = new int[5]; for(int i = 0; i < 5; i++) dist[i] = int.MaxValue; -> Option A

4. Quick Check:

   Initialize distances to max value [OK]

Hint: Initialize distances with int.MaxValue except source [OK]

Common Mistakes:

• Setting all distances to zero
• Using non-existent array methods
• Not initializing distances before algorithm

3. Consider the following DAG with edges and weights:
0 -> 1 (2), 0 -> 2 (4), 1 -> 2 (1), 1 -> 3 (7), 2 -> 4 (3), 3 -> 4 (1)
If we run the shortest path algorithm from vertex 0 using topological order, what is the shortest distance to vertex 4?

medium

A. 10

B. 6

C. 7

D. 9

Solution

1. Step 1: Find topological order and initialize distances

   Topological order can be [0,1,2,3,4]. 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[4]=3+3=6.
   From 3: dist[4]=min(6,9+1=10)=6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Shortest distance to 4 = 6 [OK]

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

Common Mistakes:

• Not updating distances after relaxation
• Using wrong topological order
• Ignoring better paths through intermediate nodes

4. The following C# code attempts to find shortest paths in a DAG but has a bug:

int[] dist = new int[V];
for(int i = 0; i < V; i++) dist[i] = int.MaxValue;
dist[source] = 0;
foreach(int u in topologicalOrder)
{
  foreach(var edge in graph[u])
  {
    int v = edge.Item1;
    int weight = edge.Item2;
    if(dist[u] + weight < dist[v])
      dist[v] = dist[u] + weight;
  }
}

What is the bug in this code?

medium

A. No check if dist[u] is int.MaxValue before adding weight

B. Edges are not relaxed in correct order

C. topologicalOrder is not computed

D. dist array is not initialized to int.MaxValue

Solution

1. Step 1: Analyze distance update condition

   The code adds dist[u] + weight without checking if dist[u] is int.MaxValue, which can cause overflow.

2. Step 2: Identify missing check

   Before adding weight, code should check if dist[u] != int.MaxValue to avoid invalid calculations.

3. Final Answer:

   No check if dist[u] is int.MaxValue before adding weight -> Option A

4. Quick Check:

   Check dist[u] before adding weight [OK]

Hint: Check dist[u] != int.MaxValue before adding weight [OK]

Common Mistakes:

• Ignoring overflow from adding to int.MaxValue
• Assuming topological order is always computed
• Thinking initialization is missing

5. Given a DAG with vertices 0 to 5 and edges:
0->1(3), 0->2(6), 1->2(4), 1->3(4), 1->4(11), 2->3(8), 3->4(-4), 4->5(2)
Using shortest path with topological order from vertex 0, what is the shortest distance to vertex 5?

hard

A. 10

B. 9

C. 7

D. 5

Solution

1. Step 1: Determine topological order and initialize distances

   Possible topological order: [0,1,2,3,4,5]. 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, dist[4]=3+11=14.
   From 2: dist[3]=min(7,6+8=14)=7.
   From 3: dist[4]=min(14,7+(-4)=3)=3.
   From 4: dist[5]=3+2=5.

3. Final Answer:

   5 -> Option D

4. Quick Check:

   Shortest distance to 5 = 5 [OK]

Hint: Relax edges in topological order, watch negative weights carefully [OK]

Common Mistakes:

• Ignoring negative edge weights
• Not updating distances after better path found
• Wrong topological order causing incorrect results