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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of shortest path distances in DAG

What is the output of the shortest path distances array after running the given Rust code on the DAG?

DSA Rust

use std::collections::VecDeque;

fn shortest_path_dag(n: usize, edges: &[(usize, usize, i32)], start: usize) -> Vec<Option<i32>> {
    let mut graph = vec![vec![]; n];
    let mut indegree = vec![0; n];
    for &(u, v, w) in edges {
        graph[u].push((v, w));
        indegree[v] += 1;
    }

    let mut dist = vec![None; n];
    dist[start] = Some(0);

    let mut queue = VecDeque::new();
    for i in 0..n {
        if indegree[i] == 0 {
            queue.push_back(i);
        }
    }

    while let Some(u) = queue.pop_front() {
        if let Some(d) = dist[u] {
            for &(v, w) in &graph[u] {
                if dist[v].is_none() || dist[v].unwrap() > d + w {
                    dist[v] = Some(d + w);
                }
                indegree[v] -= 1;
                if indegree[v] == 0 {
                    queue.push_back(v);
                }
            }
        } else {
            for &(v, _) in &graph[u] {
                indegree[v] -= 1;
                if indegree[v] == 0 {
                    queue.push_back(v);
                }
            }
        }
    }

    dist
}

fn main() {
    let n = 5;
    let edges = vec![
        (0, 1, 3),
        (0, 2, 6),
        (1, 2, 4),
        (1, 3, 4),
        (2, 3, 8),
        (1, 4, 11),
        (3, 4, -4),
    ];
    let start = 0;
    let dist = shortest_path_dag(n, &edges, start);
    println!("{:?}", dist);
}

A [Some(0), Some(3), Some(7), Some(7), Some(3)]

B [Some(0), Some(3), Some(6), Some(10), Some(6)]

C [Some(0), Some(3), Some(4), Some(8), Some(4)]

D [Some(0), Some(3), Some(7), Some(11), Some(7)]

💡 Hint

Trace the graph edges and update distances using topological order.

The shortest path distances from node 0 are calculated by relaxing edges in topological order. The distances are: 0 to 0 is 0, 0 to 1 is 3, 0 to 2 is 7 (via 1), 0 to 3 is 7 (via 1), and 0 to 4 is 3 (via 3 with negative edge).

🧠 Conceptual

intermediate

Why use topological order for shortest path in DAG?

Why is topological order important when finding shortest paths in a Directed Acyclic Graph (DAG)?

A It ensures nodes are processed only after all their predecessors, allowing correct distance updates without cycles.

B It guarantees the graph is strongly connected, so shortest paths exist between all nodes.

C It sorts nodes by their weights to prioritize heavier edges first.

D It prevents the need for edge relaxation by precomputing all distances.

💡 Hint

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

Topological order processes nodes only after all nodes leading into them are processed, ensuring that when we update distances, all shorter paths to predecessors are already known. This avoids revisiting nodes multiple times and works because DAGs have no cycles.

🔧 Debug

advanced

Identify the bug causing incorrect shortest path output

Given the Rust code below for shortest path in DAG, which option correctly identifies the bug causing wrong distances?

DSA Rust

fn shortest_path_dag_bug(n: usize, edges: &[(usize, usize, i32)], start: usize) -> Vec<Option<i32>> {
    let mut graph = vec![vec![]; n];
    let mut indegree = vec![0; n];
    for &(u, v, w) in edges {
        graph[u].push((v, w));
        indegree[v] += 1;
    }

    let mut dist = vec![None; n];
    dist[start] = Some(0);

    let mut queue = std::collections::VecDeque::new();
    for i in 0..n {
        if indegree[i] == 0 {
            queue.push_back(i);
        }
    }

    while let Some(u) = queue.pop_front() {
        for &(v, w) in &graph[u] {
            if dist[u].is_some() {
                let d = dist[u].unwrap();
                if dist[v].is_none() || dist[v].unwrap() > d + w {
                    dist[v] = Some(d + w);
                }
            }
            indegree[v] -= 1;
            if indegree[v] == 0 {
                queue.push_back(v);
            }
        }
    }

    dist
}

A The code updates distances before checking if dist[u] is Some, causing panic on unwrap.

B The code does not check if dist[u] is Some before using unwrap, risking panic.

C The code does not skip nodes with dist[u] == None, causing incorrect distance updates.

D The code does not handle negative edge weights, causing infinite loops.

💡 Hint

Look at how nodes with no known distance are processed.

The code processes all nodes regardless of whether their distance is known. Nodes with dist[u] == None should not relax edges because their distance is unknown, leading to incorrect updates.

📝 Syntax

advanced

Identify the syntax error in Rust code for shortest path in DAG

Which option contains a syntax error in the Rust code snippet for shortest path in DAG?

DSA Rust

let mut dist = vec![None; n];
dist[start] = Some(0);

for &(u, v, w) in edges {
    graph[u].push((v, w))
    indegree[v] += 1;
}

A vec![None; n] is invalid syntax for vector initialization

B Incorrect use of Some(0) instead of 0 in dist initialization

C Using & instead of &mut in for loop destructuring

D Missing semicolon after graph[u].push((v, w))

💡 Hint

Check line endings carefully in Rust code.

Rust requires semicolons at the end of statements. The line graph[u].push((v, w)) is missing a semicolon, causing a syntax error.

🚀 Application

expert

Calculate shortest path distances for a complex DAG

Given the DAG with edges and weights below, what is the shortest path distance from node 0 to node 5 after running the shortest path algorithm using topological order?

DSA Rust

Edges:
(0, 1, 2)
(0, 2, 4)
(1, 2, 1)
(1, 3, 7)
(2, 4, 3)
(3, 5, 1)
(4, 3, 2)
(4, 5, 5)

Start node: 0
Number of nodes: 6

A 7

B 9

C 10

D 8

💡 Hint

Trace shortest paths step-by-step using topological order and edge relaxation.

The shortest path from 0 to 5 is 0->1->2->4->3->5 with distances: 0->1=2, 1->2=1 (total 3), 2->4=3 (total 6), 4->3=2 (total 8), 3->5=1 (total 9). But 0->1->3->5 is 2+7+1=10, and 0->2->4->5 is 4+3+5=12. The shortest is 9 via 0->1->2->4->3->5.

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