Shortest Path in DAG Using Topological Order in DSA Java

Mental Model

We find the shortest path in a graph with no cycles by first ordering nodes so all edges go forward, then updating shortest distances step by step.

Analogy: Imagine tasks that must be done in order, like building a house. You first list tasks so each depends only on earlier ones, then find the quickest way to finish each task based on previous ones.

Graph: 0 -> 1 -> 3
       ↓    ↓
       2 -> 4

Topological order: 0 -> 1 -> 2 -> 4 -> 3

Dry Run Walkthrough

Input: Graph edges with weights: 0->1(2), 0->2(4), 1->2(1), 1->3(7), 2->4(3), 4->3(1); start node: 0

Goal: Find shortest distances from node 0 to all others using topological order

Step 1: Find topological order of nodes

Order: 0 -> 1 -> 2 -> 4 -> 3

Why: We need to process nodes so all edges go forward to update distances correctly

Step 2: Initialize distances: dist[0]=0, others=∞

dist: [0, ∞, ∞, ∞, ∞]

Why: Start node distance is zero, others unknown

Step 3: Process node 0: update dist[1]=2, dist[2]=4

dist: [0, 2, 4, ∞, ∞]

Why: Edges from 0 give initial shortest paths to 1 and 2

Step 4: Process node 1: update dist[2]=3 (min of 4 and 2+1), dist[3]=9

dist: [0, 2, 3, 9, ∞]

Why: Better path to 2 found via 1; set dist to 3 and update 3

Step 5: Process node 2: update dist[4]=6

dist: [0, 2, 3, 9, 6]

Why: From 2 to 4 is 3, so dist[4] = dist[2] + 3 = 6

Step 6: Process node 4: update dist[3]=7 (min of 9 and 6+1)

dist: [0, 2, 3, 7, 6]

Why: Better path to 3 found via 4

Step 7: Process node 3: no outgoing edges, distances unchanged

dist: [0, 2, 3, 7, 6]

Why: No further updates possible

Result:

Final shortest distances: 0 -> 0, 1 -> 2, 2 -> 3, 3 -> 7, 4 -> 6

Annotated Code

DSA Java

import java.util.*;

class Graph {
    static class Edge {
        int to, weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    int vertices;
    List<List<Edge>> adjList;

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

    void addEdge(int from, int to, int weight) {
        adjList.get(from).add(new Edge(to, weight));
    }

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

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

        // Topological sort helper
        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                topologicalSort(i, visited, stack);
            }
        }

        // Process nodes in topological order
        while (!stack.isEmpty()) {
            int u = stack.pop();
            if (dist[u] != Integer.MAX_VALUE) {
                for (Edge edge : adjList.get(u)) {
                    if (dist[u] + edge.weight < dist[edge.to]) {
                        dist[edge.to] = dist[u] + edge.weight;
                    }
                }
            }
        }

        // Print distances
        for (int i = 0; i < vertices; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.println("Distance from " + start + " to " + i + " is: Infinity");
            } else {
                System.out.println("Distance from " + start + " to " + i + " is: " + dist[i]);
            }
        }
    }

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

    public static void main(String[] args) {
        Graph g = new Graph(5);
        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, 3, 1);

        g.shortestPath(0);
    }
}

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

Perform topological sort to order nodes so edges go forward

while (!stack.isEmpty()) { int u = stack.pop(); if (dist[u] != Integer.MAX_VALUE) { for (Edge edge : adjList.get(u)) { if (dist[u] + edge.weight < dist[edge.to]) { dist[edge.to] = dist[u] + edge.weight; } } } }

Relax edges in topological order to update shortest distances

Output

Distance from 0 to 0 is: 0

Distance from 0 to 1 is: 2

Distance from 0 to 2 is: 3

Distance from 0 to 3 is: 7

Distance from 0 to 4 is: 6

Complexity Analysis

Time: O(V + E) because we do a topological sort (O(V + E)) and then relax edges once (O(E))

Space: O(V + E) for adjacency list and auxiliary data structures like stack and distance array

vs Alternative: Compared to Dijkstra's algorithm which is O(E log V), this method is faster for DAGs because it avoids priority queues by using topological order

Edge Cases

Graph with no edges

Distances remain infinity except start node which is zero

DSA Java

if (dist[u] != Integer.MAX_VALUE) {

Graph with single node

Distance to itself is zero, no updates needed

DSA Java

if (!visited[i]) { topologicalSort(i, visited, stack); }

Disconnected nodes

Distances to unreachable nodes remain infinity

DSA Java

if (dist[u] != Integer.MAX_VALUE) {

When to Use This Pattern

When you see a graph with no cycles and need shortest paths, use topological order to process nodes in a way that guarantees all edges go forward, enabling efficient distance updates.

Common Mistakes

Mistake: Not performing topological sort before relaxing edges, causing incorrect distance updates
Fix: Always run topological sort first to order nodes before relaxing edges

Mistake: Updating distances without checking if current node distance is known (not infinity)
Fix: Check if dist[u] != Integer.MAX_VALUE before relaxing edges from u

Summary

Finds shortest paths in a directed acyclic graph by processing nodes in topological order.

Use when the graph has no cycles and you want an efficient shortest path solution.

The key is to order nodes so all edges go forward, allowing one pass to update 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