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

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, how the steps increase when using topological order to find shortest paths.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn shortest_path_dag(graph: &Vec>, start: usize) -> Vec {
    let n = graph.len();
    let mut dist = vec![i32::MAX; n];
    dist[start] = 0;
    let order = topological_sort(graph);
    for &u in &order {
        if dist[u] != i32::MAX {
            for &(v, w) in &graph[u] {
                if dist[u] + w < dist[v] {
                    dist[v] = dist[u] + w;
                }
            }
        }
    }
    dist
}

This code finds the shortest path distances from a start node to all others in a DAG using topological order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The nested loops: outer loop over all nodes in topological order, inner loop over all edges from each node.
• How many times: Outer loop runs once per node (n times), inner loop runs once per outgoing edge (total m times across all nodes).

How Execution Grows With Input

As the graph grows, the number of nodes (n) and edges (m) increase, and the code checks each edge once.

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

Pattern observation: The operations grow roughly in proportion to the sum of nodes and edges.

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: "The algorithm takes O(n²) time because it has nested loops."

[OK] Correct: The inner loop does not run n times for each node; it runs once per edge overall, so total work depends on edges, not n squared.

Interview Connect

Understanding this time complexity helps you explain efficient graph algorithms clearly and confidently in interviews.

Self-Check

"What if the graph was not a DAG and contained cycles? How would the time complexity and approach change?"

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 finds the longest path instead of the shortest.

B. It guarantees the graph has cycles.

C. It sorts vertices by their weights.

D. It allows processing vertices in a linear order without revisiting nodes.

Solution

1. Step 1: Understand topological order in DAG

   Topological order arranges vertices so all edges go from earlier to later vertices, ensuring no cycles.

2. Step 2: Use topological order for shortest path

   Processing vertices in this order allows updating shortest paths without revisiting nodes, making the algorithm efficient.

3. Final Answer:

   It allows processing vertices in a linear order without revisiting nodes. -> Option D

4. Quick Check:

   Topological order = linear processing [OK]

Hint: Topological order processes nodes once in DAG [OK]

Common Mistakes:

• Thinking DAG has cycles
• Confusing topological order with sorting by weights
• Assuming it finds longest path

2. Which Rust code snippet correctly initializes a vector to store shortest distances with infinity for all vertices except the source (index 0)?

easy

A. let dist = vec![i32::MAX; n]; dist[0] = 0;

B. let dist = vec![0; n]; dist[0] = i32::MAX;

C. let dist = vec![None; n]; dist[0] = Some(0);

D. let dist = vec![0; n];

Solution

1. Step 1: Initialize distances with maximum value

   Using vec![i32::MAX; n] sets all distances to infinity (max int), representing unknown paths.

2. Step 2: Set source distance to zero

   dist[0] = 0 sets the source vertex distance to zero, as it is the start point.

3. Final Answer:

   let dist = vec![i32::MAX; n]; dist[0] = 0; -> Option A

4. Quick Check:

   Initialize with max, source zero [OK]

Hint: Use vec![i32::MAX; n] and set source to 0 [OK]

Common Mistakes:

• Setting source distance to max instead of zero
• Using zero for all distances initially
• Using Option types unnecessarily

3. Given the following Rust code snippet for shortest path in a DAG, what is the final distance vector printed?

let n = 4;
let edges = vec![
  (0, 1, 1),
  (0, 2, 4),
  (1, 2, 2),
  (1, 3, 6),
  (2, 3, 3),
];

let mut dist = vec![i32::MAX; n];
dist[0] = 0;

let topo_order = vec![0, 1, 2, 3];

for &u in &topo_order {
  for &(src, dst, w) in &edges {
    if src == u && dist[u] != i32::MAX && dist[u] + w < dist[dst] {
      dist[dst] = dist[u] + w;
    }
  }
}

println!("{:?}", dist);

medium

A. [0, 1, 4, 7]

B. [0, 1, 3, 6]

C. [0, 4, 6, 9]

D. [i32::MAX, i32::MAX, i32::MAX, i32::MAX]

Solution

1. Step 1: Initialize distances and process vertex 0

   dist = [0, MAX, MAX, MAX]. From 0: update dist[1] = 0+1=1, dist[2] = 0+4=4.

2. Step 2: Process vertex 1 and 2

   From 1: dist[2] = min(4, 1+2=3) = 3, dist[3] = 1+6=7. From 2: dist[3] = min(7, 3+3=6) = 6.

3. Step 3: Process vertex 3

   No outgoing edges, distances remain.

4. Final Answer:

   [0, 1, 3, 6] -> Option B

5. Quick Check:

   Relax edges in topo order = [0,1,3,6] [OK]

Hint: Relax edges in topological order to update distances [OK]

Common Mistakes:

• Not updating dist[2] to 3 via vertex 1
• Ignoring better path to dist[3]
• Printing distances before updates

4. Identify the bug in this Rust code snippet for shortest path in a DAG using topological order:

let n = 3;
let edges = vec![(0, 1, 5), (1, 2, 10)];
let mut dist = vec![i32::MAX; n];
dist[0] = 0;
let topo_order = vec![0, 1, 2];

for u in topo_order {
  for &(src, dst, w) in &edges {
    if src == u && dist[dst] != i32::MAX && dist[u] + w < dist[dst] {
      dist[dst] = dist[u] + w;
    }
}
}
println!("{:?}", dist);

medium

A. The condition 'dist[dst] != i32::MAX' prevents updating distances correctly.

B. The topological order vector is incorrect.

C. The initial distance vector should be zeros.

D. Edges are not represented as tuples.

Solution

1. Step 1: Analyze the if condition in edge relaxation

   The condition 'dist[dst] != i32::MAX' wrongly blocks updating dist[dst] if it is still infinity, so no update happens initially.

2. Step 2: Correct the condition to allow updates

   Remove 'dist[dst] != i32::MAX' so that if dist[u] + w is less, dist[dst] updates even if dist[dst] was infinity.

3. Final Answer:

   The condition 'dist[dst] != i32::MAX' prevents updating distances correctly. -> Option A

4. Quick Check:

   Wrong condition blocks updates [OK]

Hint: Allow updates even if dist[dst] is infinity [OK]

Common Mistakes:

• Adding unnecessary condition on dist[dst]
• Incorrect topological order
• Initializing distances with zeros

5. You have a DAG with 5 vertices and edges with weights: (0->1:2), (0->2:3), (1->3:4), (2->3:1), (3->4:5). Using topological order [0,1,2,3,4], what is the shortest path distance from vertex 0 to vertex 4?

hard

A. 11

B. 10

C. 9

D. 8

Solution

1. Step 1: Initialize distances and process vertex 0

   dist = [0, MAX, MAX, MAX, MAX]. From 0: dist[1] = 2, dist[2] = 3.

2. Step 2: Process vertex 1 and 2

   From 1: dist[3] = 2 + 4 = 6. From 2: dist[3] = min(6, 3 + 1 = 4) = 4.

3. Step 3: Process vertex 3 and 4

   From 3: dist[4] = 4 + 5 = 9. Vertex 4 has no outgoing edges.

4. Final Answer:

   9 -> Option C

5. Quick Check:

   Shortest path 0->2->3->4 = 9 [OK]

Hint: Relax edges in topo order, pick minimum sums [OK]

Common Mistakes:

• Choosing path 0->1->3->4 without checking shorter 0->2->3->4
• Adding weights incorrectly
• Ignoring topological order