Shortest Path in DAG Using Topological Order in DSA Rust - 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 city to all other cities in a network where roads only go one way and there are no loops. This network is called a Directed Acyclic Graph (DAG). You will use a special order called topological order to find the shortest paths efficiently.

🎯 Goal: Build a Rust program that finds the shortest distance from the starting city (node 0) to every other city in the DAG using topological sorting.

📋 What You'll Learn

Create a graph as an adjacency list with exact edges and weights

Create a vector to store shortest distances initialized properly

Implement topological sorting using DFS with exact variable names

Calculate shortest paths using the topological order

Print the shortest distances vector at the end

💡 Why This Matters

🌍 Real World

Finding shortest paths in networks like road maps, task scheduling, or project planning where dependencies exist and cycles are not allowed.

💼 Career

Understanding shortest path algorithms in DAGs is important for software engineers working on routing, scheduling, and optimization problems.

1

Create the DAG graph as adjacency list

Create a variable called graph as a vector of vectors of tuples. Each tuple contains a usize for the destination node and an i32 for the edge weight. Use this exact graph with 6 nodes (0 to 5) 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).

DSA Rust

// Your code here

Hint

Use a Vec of Vec of tuples. Each tuple is (destination: usize, weight: i32).

2

Create the distances vector and visited vector

Create a mutable vector called distances of type Vec with length 6. Initialize all values to i32::MAX except the first element (index 0) which should be 0. Also create a mutable vector called visited of type Vec with length 6, initialized to false.

DSA Rust

let graph: Vec> = vec![
    vec![(1, 5), (2, 3)],
    vec![(3, 6), (2, 2)],
    vec![(4, 4), (5, 2), (3, 7)],
    vec![(4, -1)],
    vec![(5, -2)],
    vec![],
];
// Your code here

Hint

Use vec![i32::MAX; 6] to initialize distances and then set distances[0] = 0. Use vec![false; 6] for visited.

3

Implement topological sort and shortest path calculation

Write a recursive function called dfs that takes node: usize, graph: &Vec>, visited: &mut Vec, and stack: &mut Vec. It marks node as visited, recursively visits all unvisited neighbors, then pushes node to stack. Then create a mutable vector stack and call dfs(0, &graph, &mut visited, &mut stack) for all nodes from 0 to 5 if not visited. After that, reverse stack. Then iterate over nodes in stack and for each neighbor (v, w), update distances[v] if distances[u] + w < distances[v].

DSA Rust

let graph: Vec> = vec![
    vec![(1, 5), (2, 3)],
    vec![(3, 6), (2, 2)],
    vec![(4, 4), (5, 2), (3, 7)],
    vec![(4, -1)],
    vec![(5, -2)],
    vec![],
];

let mut distances: Vec = vec![i32::MAX; 6];
distances[0] = 0;

let mut visited: Vec = vec![false; 6];

// Your code here

Hint

Use DFS to fill stack with nodes in topological order. Then update distances using the order in stack.

4

Print the shortest distances vector

Write a println! statement to print the distances vector.

DSA Rust

let graph: Vec> = vec![
    vec![(1, 5), (2, 3)],
    vec![(3, 6), (2, 2)],
    vec![(4, 4), (5, 2), (3, 7)],
    vec![(4, -1)],
    vec![(5, -2)],
    vec![],
];

let mut distances: Vec = vec![i32::MAX; 6];
distances[0] = 0;

let mut visited: Vec = vec![false; 6];

fn dfs(node: usize, graph: &Vec>, visited: &mut Vec, stack: &mut Vec) {
    visited[node] = true;
    for &(neighbor, _) in &graph[node] {
        if !visited[neighbor] {
            dfs(neighbor, graph, visited, stack);
        }
    }
    stack.push(node);
}

let mut stack: Vec = Vec::new();
for node in 0..6 {
    if !visited[node] {
        dfs(node, &graph, &mut visited, &mut stack);
    }
}
stack.reverse();

for &u in &stack {
    if distances[u] != i32::MAX {
        for &(v, w) in &graph[u] {
            if distances[u] + w < distances[v] {
                distances[v] = distances[u] + w;
            }
        }
    }
}
// Your code here

Hint

Use println!("{:?}", distances); to print the vector.

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