Shortest Path in DAG Using Topological Order in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of shortest path distances from source in DAG

What is the output of the following Java code that finds shortest paths from source vertex 0 in a DAG using topological order?

DSA Java

import java.util.*;

class Graph {
    int V;
    List<List<int[]>> adj;

    Graph(int V) {
        this.V = V;
        adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    void addEdge(int u, int v, int w) {
        adj.get(u).add(new int[]{v, w});
    }

    void shortestPath(int src) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        boolean[] visited = new boolean[V];
        Stack<Integer> stack = new Stack<>();

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

        while (!stack.isEmpty()) {
            int u = stack.pop();
            if (dist[u] != Integer.MAX_VALUE) {
                for (int[] edge : adj.get(u)) {
                    int v = edge[0];
                    int weight = edge[1];
                    if (dist[u] + weight < dist[v]) {
                        dist[v] = dist[u] + weight;
                    }
                }
            }
        }

        for (int i = 0; i < V; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.print("INF ");
            } else {
                System.out.print(dist[i] + " ");
            }
        }
    }

    void topologicalSort(int u, boolean[] visited, Stack<Integer> stack) {
        visited[u] = true;
        for (int[] edge : adj.get(u)) {
            int v = edge[0];
            if (!visited[v]) topologicalSort(v, visited, stack);
        }
        stack.push(u);
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph(6);
        g.addEdge(0, 1, 5);
        g.addEdge(0, 2, 3);
        g.addEdge(1, 3, 6);
        g.addEdge(1, 2, 2);
        g.addEdge(3, 4, -1);
        g.addEdge(4, 5, -2);

        g.shortestPath(0);
    }
}

A 0 5 3 12 9 7

B 0 5 3 13 9 7

C 0 5 3 11 9 7

D 0 5 3 11 10 8

💡 Hint

Trace the topological order and update distances step-by-step from source 0.

The code performs a topological sort and then relaxes edges in that order. Starting from 0, distances update as: dist[0]=0, dist[1]=5, dist[2]=3, dist[3]=11, dist[4]=10, dist[5]=8. Negative weights on edges 3->4 and 4->5 reduce distances accordingly.

🧠 Conceptual

intermediate

Why does shortest path in DAG use topological order?

Why is topological order used to find shortest paths in a Directed Acyclic Graph (DAG)?

A Because it sorts vertices by their distance values from the source.

B Because it ensures vertices are processed only after all their predecessors, allowing correct distance updates without cycles.

C Because it finds the longest path first, which helps in shortest path calculation.

D Because it groups vertices by their in-degree values.

💡 Hint

Think about how processing order affects distance updates in graphs without cycles.

Topological order processes each vertex only after all vertices leading to it are processed. This guarantees that when relaxing edges, the shortest distances to predecessors are already known, so no repeated updates or cycles occur.

🔧 Debug

advanced

Identify the bug causing incorrect shortest path output

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

DSA Java

void shortestPath(int src) {
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    Stack<Integer> stack = new Stack<>();
    boolean[] visited = new boolean[V];

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

    while (!stack.isEmpty()) {
        int u = stack.pop();
        for (int[] edge : adj.get(u)) {
            int v = edge[0];
            int weight = edge[1];
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
        }
    }
}

A The code does not check if dist[u] is Integer.MAX_VALUE before relaxing edges, causing overflow.

B The topological sort is missing a visited array, causing infinite recursion.

C The graph edges are not added before calling shortestPath.

D The distance array is not initialized with Integer.MAX_VALUE.

💡 Hint

Check what happens if dist[u] is still at initial max value when relaxing edges.

If dist[u] is Integer.MAX_VALUE, adding weight causes integer overflow and incorrect updates. The code must check dist[u] != Integer.MAX_VALUE before relaxing edges.

📝 Syntax

advanced

Identify the syntax error in this shortest path code snippet

Which option contains the syntax error in the following Java code snippet for shortest path in DAG?

DSA Java

for (int[] edge : adj.get(u)) {
    int v = edge[0];
    int weight = edge[1];
    if (dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight
    }
}

A Missing parentheses in if condition

B Incorrect array access syntax for edge elements

C Missing semicolon after dist[v] = dist[u] + weight

D Using 'for-each' loop incorrectly on adjacency list

💡 Hint

Check line endings carefully in Java.

Java statements must end with a semicolon. The line 'dist[v] = dist[u] + weight' is missing a semicolon, causing a syntax error.

🚀 Application

expert

Determine the number of vertices reachable from source after shortest path calculation

Given the DAG and source vertex 0, how many vertices have a finite shortest path distance (not INF) after running the shortest path algorithm?

DSA Java

Graph g = new Graph(7);
g.addEdge(0, 1, 2);
g.addEdge(0, 2, 4);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 7);
g.addEdge(2, 4, 3);
g.addEdge(4, 5, 1);
g.addEdge(5, 6, 5);
// Vertex 6 has no outgoing edges
// Vertex 3 has no outgoing edges
// Vertex 6 is reachable only through 5
// Vertex 3 is reachable through 1
// Vertex 0 is source
// Vertex unreachable: none

// Run shortestPath(0) and count vertices with dist != INF

A 7

B 6

C 5

D 4

💡 Hint

Check connectivity from source 0 to all vertices.

All vertices 0 through 6 are reachable from source 0 through edges. So all have finite shortest path 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