Bird
Raised Fist0
DSA Javaprogramming~5 mins

Shortest Path in DAG Using Topological Order in DSA Java - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Shortest Path in DAG Using Topological Order
O(n + m)
Understanding Time Complexity

We want to understand how the time needed to find the shortest path in a Directed Acyclic Graph (DAG) grows as the graph gets bigger.

Specifically, we ask: how does the number of steps change when the graph has more nodes and edges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


// Find shortest paths in DAG using topological order
void shortestPath(int src, List> graph, int[] dist) {
    int n = graph.size();
    boolean[] visited = new boolean[n];
    Stack stack = new Stack<>();
    
    // Step 1: Topological sort
    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfs(i, graph, visited, stack);
    }

    // Step 2: Initialize distances
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    // Step 3: Relax edges in topological order
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (dist[u] != Integer.MAX_VALUE) {
            for (Edge e : graph.get(u)) {
                if (dist[u] + e.weight < dist[e.to]) {
                    dist[e.to] = dist[u] + e.weight;
                }
            }
        }
    }
}

void dfs(int u, List> graph, boolean[] visited, Stack stack) {
    visited[u] = true;
    for (Edge e : graph.get(u)) {
        if (!visited[e.to]) dfs(e.to, graph, visited, stack);
    }
    stack.push(u);
}

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

This code finds shortest paths from a source node to all others in a DAG by first sorting nodes topologically, then relaxing edges in that order.

Identify Repeating Operations

Look at the parts that repeat work:

  • Primary operation: Visiting each node and edge once during DFS and edge relaxation.
  • How many times: Each node is visited once in DFS; each edge is checked once during relaxation.
How Execution Grows With Input

As the graph grows, the work grows with the number of nodes and edges.

Input Size (n nodes, m edges)Approx. Operations
10 nodes, 15 edgesAbout 25 steps (10 nodes + 15 edges)
100 nodes, 200 edgesAbout 300 steps (100 + 200)
1000 nodes, 5000 edgesAbout 6000 steps (1000 + 5000)

Pattern observation: The steps grow roughly by adding nodes and edges, so more nodes and edges mean more work, but each is handled once.

Final Time Complexity

Time Complexity: O(n + m)

This means the time to find shortest paths grows linearly with the number of nodes plus the number of edges in the graph.

Common Mistake

[X] Wrong: "Since we check edges inside a loop, the time must be quadratic like O(n²)."

[OK] Correct: We only visit each edge once during relaxation, not inside nested loops over all nodes, so the total work is linear in edges, not squared.

Interview Connect

Understanding this linear time approach shows you can efficiently handle graphs without cycles, a common real-world scenario. It builds confidence in working with graph algorithms and their performance.

Self-Check

"What if the graph had cycles? How would that affect the time complexity and approach?"

Practice

(1/5)
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
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard