Shortest Path in DAG Using Topological Order in DSA Rust

Mental Model

In a graph with no cycles, we can find the shortest path by visiting nodes in order where all edges go forward, updating distances as we go.

Analogy: Imagine a line of dominoes set up so each domino can only knock down the next ones ahead, never behind. By pushing them in order, you know exactly how far the push travels to each domino.

0 -> 1 -> 2 -> 3 -> null
↑ topological order
Distances update as we move forward

Dry Run Walkthrough

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

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

Step 1: Compute topological order: [0, 1, 2, 3]

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

Why: We must 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 yet

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

dist: [0, 2, 4, ∞]

Why: Edges from 0 give direct distances to 1 and 2

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

dist: [0, 2, 3, 9]

Why: Better path to 2 found via 1; set distance to 3

Step 5: Process node 2: update dist[3]=min(9, 3+3=6)=6

dist: [0, 2, 3, 6]

Why: Better path to 3 found via 2

Step 6: Process node 3: no outgoing edges

dist: [0, 2, 3, 6]

Why: No updates needed

Result:

Final distances: 0 -> 0, 1 -> 2, 2 -> 3, 3 -> 6

Annotated Code

DSA Rust

use std::collections::VecDeque;

struct Edge {
    to: usize,
    weight: i32,
}

fn shortest_path_dag(graph: &Vec<Vec<Edge>>, start: usize) -> Vec<Option<i32>> {
    let n = graph.len();
    let mut indegree = vec![0; n];
    for edges in graph.iter() {
        for edge in edges.iter() {
            indegree[edge.to] += 1;
        }
    }

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

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

    while let Some(u) = queue.pop_front() {
        if let Some(u_dist) = dist[u] {
            for edge in &graph[u] {
                let v = edge.to;
                let w = edge.weight;
                if dist[v].is_none() || dist[v].unwrap() > u_dist + w {
                    dist[v] = Some(u_dist + w);
                }
                indegree[v] -= 1;
                if indegree[v] == 0 {
                    queue.push_back(v);
                }
            }
        } else {
            // Node unreachable from start, just reduce indegree
            for edge in &graph[u] {
                indegree[edge.to] -= 1;
                if indegree[edge.to] == 0 {
                    queue.push_back(edge.to);
                }
            }
        }
    }

    dist
}

fn main() {
    // Graph: 0->1(2), 0->2(4), 1->2(1), 1->3(7), 2->3(3)
    let graph = vec![
        vec![Edge { to: 1, weight: 2 }, Edge { to: 2, weight: 4 }],
        vec![Edge { to: 2, weight: 1 }, Edge { to: 3, weight: 7 }],
        vec![Edge { to: 3, weight: 3 }],
        vec![],
    ];

    let dist = shortest_path_dag(&graph, 0);

    for (i, d) in dist.iter().enumerate() {
        match d {
            Some(val) => println!("Distance from 0 to {} is {}", i, val),
            None => println!("Node {} is unreachable from 0", i),
        }
    }
}

for edges in graph.iter() { for edge in edges.iter() { indegree[edge.to] += 1; } }

Calculate indegree for each node to find starting points

for i in 0..n { if indegree[i] == 0 { queue.push_back(i); } }

Add nodes with zero indegree to queue for topological order

dist[start] = Some(0);

Initialize start node distance to zero

while let Some(u) = queue.pop_front() {

Process nodes in topological order

if let Some(u_dist) = dist[u] {

Only update neighbors if current node is reachable

if dist[v].is_none() || dist[v].unwrap() > u_dist + w { dist[v] = Some(u_dist + w); }

Relax edge if shorter path found

indegree[v] -= 1; if indegree[v] == 0 { queue.push_back(v); }

Decrease indegree and add to queue if zero

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 6

Complexity Analysis

Time: O(V + E) because we visit each node and edge once in topological order

Space: O(V + E) for storing graph and auxiliary arrays like indegree and distance

vs Alternative: Compared to Dijkstra's algorithm, this is faster for DAGs because no priority queue is needed

Edge Cases

Graph with unreachable nodes from start

Distances remain None for unreachable nodes

DSA Rust

if let Some(u_dist) = dist[u] { ... } else { ... }

Graph with single node and no edges

Distance to start node is zero, others do not exist

DSA Rust

dist[start] = Some(0);

Graph with multiple edges to same node

Shortest distance is chosen by relaxing edges

DSA Rust

if dist[v].is_none() || dist[v].unwrap() > u_dist + w { dist[v] = Some(u_dist + w); }

When to Use This Pattern

When you see a graph with no cycles and need shortest paths, use topological order to process nodes once and relax edges efficiently.

Common Mistakes

Mistake: Not initializing distances properly, causing unreachable nodes to have incorrect values
Fix: Initialize distances with None and set start node distance to zero explicitly

Mistake: Processing nodes without considering indegree, breaking topological order
Fix: Use indegree counts and queue to ensure nodes are processed only after all predecessors

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 efficient shortest path calculation.

The key insight is that topological order guarantees all edges go forward, so distances can be updated once per node.

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