Shortest Path in DAG Using Topological Order in DSA Java - 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

↓

Repeat until all nodes processed

↓

Distances array has shortest paths

Build graph, find topological order, then relax edges in that order to find shortest paths.

Execution Sample

DSA Java

int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
for (int u : topoOrder) {
  for (Edge e : graph[u]) {
    if (dist[u] != Integer.MAX_VALUE && dist[u] + e.weight < dist[e.to])
      dist[e.to] = dist[u] + e.weight;
  }
}

Initialize distances, then relax edges in topological order to find shortest paths.

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, ∞, ∞, ∞, ∞]	0 -> ∞ -> ∞ -> ∞ -> ∞
2	Process node 0	0	0->1 (weight 3)	dist[1]=0+3=3	[0, 3, ∞, ∞, ∞]	0 -> 3 -> ∞ -> ∞ -> ∞
3	Process node 0	0	0->2 (weight 6)	dist[2]=0+6=6	[0, 3, 6, ∞, ∞]	0 -> 3 -> 6 -> ∞ -> ∞
4	Process node 1	1	1->2 (weight 4)	dist[2]=min(6,3+4=7)=6 (no update)	[0, 3, 6, ∞, ∞]	0 -> 3 -> 6 -> ∞ -> ∞
5	Process node 1	1	1->3 (weight 4)	dist[3]=3+4=7	[0, 3, 6, 7, ∞]	0 -> 3 -> 6 -> 7 -> ∞
6	Process node 2	2	2->4 (weight 2)	dist[4]=6+2=8	[0, 3, 6, 7, 8]	0 -> 3 -> 6 -> 7 -> 8
7	Process node 3	3	3->4 (weight 1)	dist[4]=min(8,7+1=8)=8 (no update)	[0, 3, 6, 7, 8]	0 -> 3 -> 6 -> 7 -> 8
8	Process node 4	4	No outgoing edges	No update	[0, 3, 6, 7, 8]	0 -> 3 -> 6 -> 7 -> 8
9	End	N/A	N/A	All nodes processed	[0, 3, 6, 7, 8]	Final shortest distances

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

Variable Tracker

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

Key Moments - 3 Insights

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

Because we don't know any path to other nodes yet, so we set them as unreachable (∞). See Step 1 in execution_table where dist array is set.

Why do we process nodes in topological order?

Because in a DAG, processing nodes in topological order ensures all edges from earlier nodes are relaxed before later nodes. See Steps 2-8 where nodes are processed in topo order.

Why do some distance updates not change the value?

Because the new path is not shorter than the current known path. For example, Step 4 shows no update since 6 < 7.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the distance to node 3?

A ∞

B 3

C 7

D 8

💡 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 6

B Step 7

C Step 4

D Step 2

💡 Hint

Look for the first time dist[4] changes from ∞ in execution_table.

If the edge 1->2 had weight 1 instead of 4, what would be the distance to node 2 after Step 4?

A 3

B 4

C 7

D ∞

💡 Hint

Check how relaxation updates dist[2] comparing current dist and dist[1]+weight at Step 4.

Concept Snapshot

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

Full Transcript

This concept finds shortest paths in a Directed Acyclic Graph (DAG) using topological order. First, we build the graph with edges and weights. 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 the start node distance as zero and others as infinity, meaning unreachable. Next, we process each node in topological order and relax all edges from that node. Relaxing means checking if going through the current node gives a shorter path to the connected node, and if yes, updating 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. The execution table shows step-by-step how distances update and nodes are processed. Key moments clarify why initialization uses infinity, why topological order is important, and why some updates do not change distances. The visual quiz tests understanding of distance updates and order of processing.

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 vertices by their weights.

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 every directed edge goes from an earlier vertex to a later one, 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 nodes.

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 correct sequence [OK]

Common Mistakes:

• Thinking topological order sorts by weights
• Assuming DAG has cycles
• Confusing shortest path with longest path

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

easy

A. int[] dist = new int[5]; Arrays.fill(dist, Integer.MIN_VALUE); dist[0] = 0;

B. int[] dist = new int[5]; Arrays.fill(dist, 0); dist[0] = Integer.MAX_VALUE;

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

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

Solution

1. Step 1: Initialize distances to max value

   Distances to all vertices except source should be set to Integer.MAX_VALUE to represent infinity.

2. Step 2: Set source distance to zero

   Distance to source vertex 0 must be zero as it is the starting point.

3. Final Answer:

   int[] dist = new int[5]; for(int i=0; i<5; i++) dist[i] = Integer.MAX_VALUE; dist[0] = 0; -> Option D

4. Quick Check:

   Initialize all to max, source to zero [OK]

Hint: Set all distances max except source zero [OK]

Common Mistakes:

• Setting all distances to zero
• Setting source distance to max value
• Using Integer.MIN_VALUE instead of max

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)
Using topological order [0,1,2,3,4], what is the shortest distance array from source 0 after processing?

medium

A. [0, 2, 3, 7, 6]

B. [0, 2, 4, 7, 8]

C. [0, 2, 3, 9, 6]

D. [0, 2, 5, 8, 9]

Solution

1. Step 1: Initialize distances and process vertex 0

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

2. Step 2: Process vertex 1 and 2

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

3. Step 3: Process vertex 3 and 4

   From 3: dist[4]=min(6,9+1)=6 (unchanged). Final dist = [0,2,3,9,6].

4. Final Answer:

   [0, 2, 3, 9, 6] -> Option C

5. Quick Check:

   Relax edges in topological order = [0,2,3,9,6] [OK]

Hint: Relax edges in topological order updating distances [OK]

Common Mistakes:

• Not updating dist[2] from 1->2 edge
• Incorrectly updating dist[4] from 3->4
• Mixing up edge weights

4. Given this Java code snippet for shortest path in DAG, what is the error?

for(int u : topoOrder) {
  for(Edge e : graph[u]) {
    if(dist[u] + e.weight < dist[e.dest]) {
      dist[e.dest] = dist[u] + e.weight;
    }
  }
}

Assume dist array and topoOrder are correct.

medium

A. The code does not initialize dist array properly.

B. No error; code correctly relaxes edges in topological order.

C. The inner loop should iterate over graph[e.dest], not graph[u].

D. The condition should use > instead of < for shortest path.

Solution

1. Step 1: Check loop structure and relaxation logic

   Outer loop iterates vertices in topological order. Inner loop relaxes edges from u to e.dest.

2. Step 2: Verify relaxation condition

   Condition dist[u] + e.weight < dist[e.dest] correctly updates shorter distances.

3. Final Answer:

   No error; code correctly relaxes edges in topological order. -> Option B

4. Quick Check:

   Relax edges with correct condition and loops [OK]

Hint: Relax edges with dist[u]+weight < dist[v] in topo order [OK]

Common Mistakes:

• Confusing graph[u] with graph[e.dest]
• Using wrong comparison operator
• Forgetting to initialize dist array

5. You have a DAG with 6 vertices and edges:
0->1(5), 0->2(3), 1->3(6), 1->2(2), 2->4(4), 2->5(2), 2->3(7), 3->4(-1), 4->5(-2)
If you run shortest path using topological order starting from vertex 0, what is the shortest distance to vertex 5?

hard

A. 5

B. 4

C. 3

D. 7

Solution

1. Step 1: Initialize distances and process vertex 0

   dist = [0, ∞, ∞, ∞, ∞, ∞]. From 0: dist[1]=5, dist[2]=3.

2. Step 2: Process vertex 1 and 2

   From 1: dist[3]=min(∞,5+6)=11, dist[2]=min(3,5+2)=3 (unchanged). From 2: dist[4]=3+4=7, dist[5]=3+2=5, dist[3]=min(11,3+7)=10.

3. Step 3: Process vertex 3 and 4

   From 3: dist[4]=min(7,10+(-1))=7 (7 is smaller, so remains 7). From 4: dist[5]=min(5,7+(-2))=5 (5 is smaller, remains 5).

4. Step 4: Final shortest distance to vertex 5

   After all relaxations, dist[5] = 5.

5. Final Answer:

   5 -> Option A

6. Quick Check:

   Relax edges carefully with negative weights in DAG [OK]

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

Common Mistakes:

• Ignoring negative edge weights
• Not updating distances after negative edges
• Assuming negative cycles exist in DAG