Shortest Path in DAG Using Topological Order in DSA Java - Build from Scratch

Shortest Path in DAG Using Topological Order

📖 Scenario: You are working on a project to find the shortest path from a starting point to all other points in a network that has no cycles (a Directed Acyclic Graph or DAG). This is useful in scheduling tasks where some tasks must be done before others.

🎯 Goal: Build a Java program that finds the shortest distance from a source node to all other nodes in a DAG using topological sorting.

📋 What You'll Learn

Create a graph using adjacency list representation with weights

Use a topological sort to order the nodes

Calculate shortest paths from the source node using the topological order

Print the shortest distances from the source to all nodes

💡 Why This Matters

🌍 Real World

Finding shortest paths in DAGs is useful in project scheduling, task ordering, and optimizing workflows where some tasks depend on others.

💼 Career

Understanding shortest path algorithms and topological sorting is important for software engineers working on compilers, build systems, and dependency resolution.

1

Create the graph data structure

Create an adjacency list called graph as an ArrayList of ArrayList<int[]> with 6 nodes (0 to 5). Add these edges with weights exactly:
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).

DSA Java

import java.util.*;

public class ShortestPathDAG {
    public static void main(String[] args) {
        // Create an adjacency list called graph with 6 nodes
        // Add edges with weights as specified
        // Your code here
    }
}

Hint

Use an ArrayList of ArrayList<int[]> to store edges and weights. Each int[] holds two values: destination node and weight.

2

Create a distance array and source node

Create an integer array called dist of size 6 and initialize all values to Integer.MAX_VALUE. Then create an integer variable called source and set it to 1. Set dist[source] to 0.

DSA Java

import java.util.*;

public class ShortestPathDAG {
    public static void main(String[] args) {
        int n = 6;
        ArrayList> graph = new ArrayList();
        for (int i = 0; i ());
        }
        graph.get(0).add(new int[]{1, 5});
        graph.get(0).add(new int[]{2, 3});
        graph.get(1).add(new int[]{3, 6});
        graph.get(1).add(new int[]{2, 2});
        graph.get(2).add(new int[]{4, 4});
        graph.get(2).add(new int[]{5, 2});
        graph.get(2).add(new int[]{3, 7});
        graph.get(3).add(new int[]{4, -1});
        graph.get(4).add(new int[]{5, -2});
        // Create dist array and source variable
        // Your code here
    }
}

Hint

Use Arrays.fill(dist, Integer.MAX_VALUE) to set all distances to a large number. Set the source node distance to 0.

3

Implement topological sort and shortest path calculation

Write a method called topologicalSort that takes graph and n as parameters and returns an ArrayList<Integer> with nodes in topological order. Then, in main, call topologicalSort(graph, n) and store the result in topOrder. Use topOrder to update dist for shortest paths by relaxing edges.

DSA Java

import java.util.*;

public class ShortestPathDAG {
    public static void main(String[] args) {
        int n = 6;
        ArrayList> graph = new ArrayList();
        for (int i = 0; i ());
        }
        graph.get(0).add(new int[]{1, 5});
        graph.get(0).add(new int[]{2, 3});
        graph.get(1).add(new int[]{3, 6});
        graph.get(1).add(new int[]{2, 2});
        graph.get(2).add(new int[]{4, 4});
        graph.get(2).add(new int[]{5, 2});
        graph.get(2).add(new int[]{3, 7});
        graph.get(3).add(new int[]{4, -1});
        graph.get(4).add(new int[]{5, -2});

        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        int source = 1;
        dist[source] = 0;

        // Call topologicalSort and update dist using topOrder
        // Your code here
    }

    // Define topologicalSort method below
    // Your code here
}

Hint

Calculate indegrees, use a queue for nodes with zero indegree, and build the topological order. Then relax edges in that order to find shortest paths.

4

Print the shortest distances

Use a for loop with variable i from 0 to 5 to print the shortest distance from source to node i. If dist[i] is Integer.MAX_VALUE, print "INF" instead of the distance.

DSA Java

import java.util.*;

public class ShortestPathDAG {
    public static void main(String[] args) {
        int n = 6;
        ArrayList> graph = new ArrayList();
        for (int i = 0; i ());
        }
        graph.get(0).add(new int[]{1, 5});
        graph.get(0).add(new int[]{2, 3});
        graph.get(1).add(new int[]{3, 6});
        graph.get(1).add(new int[]{2, 2});
        graph.get(2).add(new int[]{4, 4});
        graph.get(2).add(new int[]{5, 2});
        graph.get(2).add(new int[]{3, 7});
        graph.get(3).add(new int[]{4, -1});
        graph.get(4).add(new int[]{5, -2});

        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        int source = 1;
        dist[source] = 0;

        ArrayList topOrder = topologicalSort(graph, n);

        for (int node : topOrder) {
            if (dist[node] != Integer.MAX_VALUE) {
                for (int[] edge : graph.get(node)) {
                    int v = edge[0];
                    int weight = edge[1];
                    if (dist[node] + weight  topologicalSort(ArrayList> graph, int n) {
        int[] indegree = new int[n];
        for (int i = 0; i  queue = new LinkedList();
        for (int i = 0; i  topOrder = new ArrayList();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            topOrder.add(node);
            for (int[] edge : graph.get(node)) {
                int v = edge[0];
                indegree[v]--;
                if (indegree[v] == 0) {
                    queue.add(v);
                }
            }
        }
        return topOrder;
    }
}

Hint

Loop through all nodes and print their distance. If distance is Integer.MAX_VALUE, print "INF".

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