Shortest Path in DAG Using Topological Order in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance array with infinity values.

DSA Java

int[] dist = new int[V];
for (int i = 0; i < V; i++) {
    dist[i] = [1];
}

Drag options to blanks, or click blank then click option'

A-1

B0

CInteger.MAX_VALUE

DInteger.MIN_VALUE

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of infinity causes incorrect shortest path calculations.

Using negative values can cause wrong results.

We use Integer.MAX_VALUE to represent infinity for initial distances.

2fill in blank

medium

Complete the code to relax edges during shortest path calculation.

DSA Java

for (Pair neighbor : adj.get(u)) {
    int v = neighbor.getKey();
    int weight = neighbor.getValue();
    if (dist[u] != Integer.MAX_VALUE && dist[u] + [1] < dist[v]) {
        dist[v] = dist[u] + weight;
    }
}

Drag options to blanks, or click blank then click option'

Aweight

Bv

Cu

Ddist[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong variable instead of weight.

Adding dist[v] instead of weight.

The edge weight is added to the current distance to relax the edge.

3fill in blank

hard

Fix the error in the topological sort DFS call to correctly process all vertices.

DSA Java

for (int i = 0; i < V; i++) {
    if (!visited[i]) {
        [1](i, visited, stack, adj);
    }
}

Drag options to blanks, or click blank then click option'

AtopologicalSortDFS

BshortestPath

CrelaxEdges

DinitializeDist

Attempts:

3 left

💡 Hint

Common Mistakes

Calling the wrong function name causes compilation errors.

Not calling DFS for all unvisited vertices.

The DFS function for topological sorting is called topologicalSortDFS.

4fill in blank

hard

Fill both blanks to complete the loop that processes vertices in topological order.

DSA Java

while (!stack.isEmpty()) {
    int u = stack.[1]();
    for (Pair neighbor : adj.get(u)) {
        int v = neighbor.[2]();
        int weight = neighbor.getValue();
        if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
            dist[v] = dist[u] + weight;
        }
    }
}

Drag options to blanks, or click blank then click option'

Apop

Bpeek

CgetKey

DgetValue

Attempts:

3 left

💡 Hint

Common Mistakes

Using peek() instead of pop() causes infinite loop.

Using getValue() instead of getKey() for vertex.

We pop vertices from the stack and get the key (vertex) from the neighbor pair.

5fill in blank

hard

Fill all three blanks to complete the initialization and update of the distance array.

DSA Java

int[] dist = new int[V];
for (int i = 0; i < V; i++) {
    dist[i] = [1];
}
dist[[2]] = 0;

// Relax edges in topological order
while (!stack.isEmpty()) {
    int u = stack.pop();
    if (dist[u] != Integer.MAX_VALUE) {
        for (Pair neighbor : adj.get(u)) {
            int v = neighbor.getKey();
            int weight = neighbor.getValue();
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + [3];
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

AInteger.MAX_VALUE

Bsource

Cweight

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Not setting source distance to zero.

Adding wrong value instead of weight during relaxation.

Initialize distances with infinity, set source distance to 0, and add edge weight when relaxing.

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