Shortest Path in DAG Using Topological Order in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Directed Acyclic Graph (DAG)?

A Directed Acyclic Graph (DAG) is a graph with directed edges and no cycles, meaning you cannot start at one node and follow a path that loops back to the same node.

intermediate

Why do we use topological order for shortest path in a DAG?

Topological order arranges nodes so that all edges go from earlier to later nodes. This order helps find shortest paths efficiently by relaxing edges only once in the correct sequence.

beginner

What does 'relaxing an edge' mean in shortest path algorithms?

Relaxing an edge means checking if the current known distance to a node can be improved by going through another node, and updating the distance if it is shorter.

intermediate

What is the time complexity of finding shortest paths in a DAG using topological order?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because each node and edge is processed once.

beginner

In the context of shortest path in DAG, what initial distance values do we assign before processing?

We set the distance to the source node as 0 and all other nodes as infinity (or a very large number) to indicate they are not yet reachable.

What property must a graph have to use topological order for shortest path?

A It must be a complete graph

B It must be an undirected graph

C It must be a Directed Acyclic Graph (DAG)

D It must contain cycles

Topological order only exists for Directed Acyclic Graphs (DAGs), so shortest path using topological order requires the graph to be a DAG.

What is the first step in finding shortest paths in a DAG using topological order?

A Relax all edges randomly

B Find the topological order of the nodes

C Initialize all distances to zero

D Run Dijkstra's algorithm

The first step is to find the topological order of the nodes to process them in the correct sequence.

When relaxing edges in topological order, how many times is each edge processed?

A Once

B Twice

C Multiple times until no changes

D Never

Each edge is relaxed exactly once in topological order, making the algorithm efficient.

What initial distance value is assigned to nodes other than the source?

A Random value

B Zero

C Negative one

D Infinity (a very large number)

Nodes other than the source start with distance infinity to indicate they are not reachable yet.

What is the main advantage of using topological order for shortest path in DAGs?

A It allows processing nodes in a sequence that guarantees correct shortest paths with one pass

B It works for graphs with cycles

C It requires no initialization

D It uses more memory

Topological order ensures nodes are processed so that all edges go forward, allowing shortest paths to be found in one pass.

Explain how topological order helps in finding the shortest path in a DAG.

Think about how ordering nodes prevents revisiting and cycles.

Describe the steps to find shortest paths in a DAG using topological order.

Start from initialization and end with final distances.

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