Dijkstra's Algorithm Single Source Shortest Path in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dijkstra's Algorithm on a Simple Graph

Given the Rust code implementing Dijkstra's algorithm on a graph with 4 nodes, what is the shortest distance array output from source node 0?

DSA Rust

use std::collections::BinaryHeap;
use std::cmp::Ordering;

#[derive(Copy, Clone, Eq, PartialEq)]
struct State {
    cost: usize,
    position: usize,
}

impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering {
        other.cost.cmp(&self.cost)
            .then_with(|| self.position.cmp(&other.position))
    }
}

impl PartialOrd for State {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn dijkstra(adj_list: &Vec<Vec<(usize, usize)>>, start: usize) -> Vec<usize> {
    let mut dist = vec![usize::MAX; adj_list.len()];
    let mut heap = BinaryHeap::new();

    dist[start] = 0;
    heap.push(State { cost: 0, position: start });

    while let Some(State { cost, position }) = heap.pop() {
        if cost > dist[position] {
            continue;
        }

        for &(neighbor, weight) in &adj_list[position] {
            let next = State { cost: cost + weight, position: neighbor };

            if next.cost < dist[neighbor] {
                dist[neighbor] = next.cost;
                heap.push(next);
            }
        }
    }

    dist
}

fn main() {
    let graph = vec![
        vec![(1, 2), (2, 4)],
        vec![(2, 1), (3, 7)],
        vec![(3, 3)],
        vec![],
    ];

    let distances = dijkstra(&graph, 0);
    println!("{:?}", distances);
}

A [0, 2, 3, 6]

B [0, 2, 4, 7]

C [0, 4, 5, 8]

D [0, 3, 4, 7]

💡 Hint

Trace the shortest paths from node 0 to others considering edge weights.

The shortest distances from node 0 are: to node 1 is 2, to node 2 is 3 (via node 1), and to node 3 is 6 (via nodes 1 and 2).

🧠 Conceptual

intermediate

Understanding Priority Queue Role in Dijkstra's Algorithm

What is the main purpose of using a priority queue (BinaryHeap) in Dijkstra's algorithm implementation?

A To always select the next node with the smallest current distance to process.

B To sort edges by their weights before processing.

C To keep track of visited nodes only.

D To store all nodes in alphabetical order for traversal.

💡 Hint

Think about how the algorithm picks which node to explore next.

The priority queue ensures the algorithm always processes the node with the smallest known distance next, which is essential for correctness and efficiency.

🔧 Debug

advanced

Identify the Bug in Dijkstra's Algorithm Implementation

Consider this Rust code snippet from a Dijkstra's algorithm implementation. What error will it cause when run?

DSA Rust

fn dijkstra(adj_list: &Vec<Vec<(usize, usize)>>, start: usize) -> Vec<usize> {
    let mut dist = vec![usize::MAX; adj_list.len()];
    let mut heap = BinaryHeap::new();

    dist[start] = 0;
    heap.push(State { cost: 0, position: start });

    while let Some(State { cost, position }) = heap.pop() {
        if cost > dist[position] {
            continue;
        }

        for &(neighbor, weight) in &adj_list[position] {
            let next = State { cost: cost + weight, position: neighbor };

            if next.cost < dist[neighbor] {
                dist[neighbor] = next.cost;
                heap.push(next);
            }
        }
    }

    dist
}

A It will cause a runtime panic due to index out of bounds.

B The algorithm will run incorrectly and produce wrong shortest distances.

C It will cause an infinite loop because the heap is never emptied.

D It will cause a compile-time error due to missing trait implementations.

💡 Hint

Look carefully at the condition that skips processing nodes.

The condition 'if cost < dist[position]' is incorrect. It should be 'if cost > dist[position]' to skip outdated entries. This bug causes the algorithm to process nodes with outdated distances, leading to wrong results.

❓ Predict Output

advanced

Output of Dijkstra's Algorithm with Unreachable Nodes

What is the output distance vector when running Dijkstra's algorithm from node 0 on this graph with 5 nodes, where node 4 is disconnected?

DSA Rust

fn main() {
    let graph = vec![
        vec![(1, 10), (2, 3)],
        vec![(2, 1), (3, 2)],
        vec![(1, 4), (3, 8), (4, 2)],
        vec![(4, 7)],
        vec![],
    ];

    let distances = dijkstra(&graph, 0);
    println!("{:?}", distances);
}

A [0, 7, 3, 9, 7]

B [0, 10, 3, 11, 7]

C [0, 7, 3, 9, 5]

D [0, 10, 3, 11, 18446744073709551615]

💡 Hint

Consider the shortest paths and the disconnected node's distance.

Node 4 is reachable via node 2 with total cost 5 (3 + 2). Distances are [0,7,3,9,5].

🧠 Conceptual

expert

Why Dijkstra's Algorithm Fails with Negative Edge Weights

Why does Dijkstra's algorithm not work correctly if the graph contains edges with negative weights?

A Because negative weights cause infinite loops in the algorithm.

B Because the priority queue cannot handle negative numbers.

C Because the algorithm requires all edge weights to be zero or positive for sorting.

D Because it assumes once a node's shortest distance is found, it cannot be improved, which is false with negative edges.

💡 Hint

Think about the assumption Dijkstra's algorithm makes about distances.

Dijkstra's algorithm assumes that once a node is visited with the smallest distance, no shorter path to it exists. Negative edges can violate this assumption by allowing shorter paths after visiting.

Practice

1. What is the main purpose of Dijkstra's Algorithm in graph theory?

easy

A. To find the shortest path from a single source to all other vertices

B. To find the maximum flow in a network

C. To detect cycles in a graph

D. To sort vertices in topological order

Solution

1. Step 1: Understand the algorithm's goal

   Dijkstra's Algorithm is designed to find the shortest paths from one starting point to all other points in a graph with non-negative edge weights.

2. Step 2: Compare with other graph algorithms

   Other options like maximum flow, cycle detection, and topological sorting serve different purposes unrelated to shortest paths.

3. Final Answer:

   To find the shortest path from a single source to all other vertices -> Option A

4. Quick Check:

   Dijkstra's Algorithm = shortest path from single source [OK]

Hint: Remember: Dijkstra finds shortest paths from one start [OK]

Common Mistakes:

• Confusing with algorithms for max flow or cycle detection
• Thinking it sorts vertices instead of finding paths
• Assuming it works with negative weights

2. Which Rust data structure is most suitable to efficiently pick the next vertex with the smallest tentative distance in Dijkstra's Algorithm?

easy

A. HashMap

B. VecDeque

C. BinaryHeap

D. LinkedList

Solution

1. Step 1: Identify the need for priority selection

   Dijkstra's Algorithm requires repeatedly selecting the vertex with the smallest tentative distance efficiently.

2. Step 2: Choose the appropriate Rust data structure

   BinaryHeap is a priority queue in Rust that allows efficient extraction of the smallest or largest element, suitable for this purpose.

3. Final Answer:

   BinaryHeap -> Option C

4. Quick Check:

   Priority queue = BinaryHeap [OK]

Hint: Use BinaryHeap for priority queue in Rust [OK]

Common Mistakes:

• Using VecDeque which is a queue, not priority queue
• Using HashMap which stores key-value pairs but no priority
• Using LinkedList which is inefficient for priority access

3. What will be the output distances array after running Dijkstra's Algorithm from source vertex 0 on this graph represented as adjacency list?

let graph = vec![
  vec![(1, 4), (2, 1)],
  vec![(3, 1)],
  vec![(1, 2), (3, 5)],
  vec![]
];

Options show distances from vertex 0 to vertices 0,1,2,3.

medium

A. [0, 4, 1, 6]

B. [0, 3, 1, 4]

C. [0, 2, 1, 3]

D. [0, 1, 2, 5]

Solution

1. Step 1: Initialize distances and process neighbors

   Start at vertex 0 with distance 0. Neighbors: vertex 1 (4), vertex 2 (1). Distances: [0,4,1,∞]

2. Step 2: Pick vertex with smallest distance and update

   Pick vertex 2 (distance 1). Update vertex 1 via 2: 1 + 2 = 3 (less than 4), update vertex 3 via 2: 1 + 5 = 6. Distances: [0,3,1,6]

3. Step 3: Pick vertex 1 (distance 3) and update

   From vertex 1 to 3: 3 + 1 = 4 (less than 6), update vertex 3 distance to 4. Distances: [0,3,1,4]

4. Final Answer:

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

5. Quick Check:

   Shortest distances from 0 = [0,3,1,4] [OK]

Hint: Update distances only if new path is shorter [OK]

Common Mistakes:

• Not updating vertex 1 distance via vertex 2
• Ignoring better path to vertex 3 through vertex 1
• Confusing edge weights or directions

4. Identify the bug in this Rust snippet implementing Dijkstra's Algorithm and select the correct fix:

let mut dist = vec![usize::MAX; graph.len()];
dist[source] = 0;
let mut heap = BinaryHeap::new();
heap.push((0, source));

while let Some((cost, u)) = heap.pop() {
  if cost > dist[u] { continue; }
  for &(v, w) in &graph[u] {
    let next = cost + w;
    if next < dist[v] {
      dist[v] = next;
      heap.push((next, v));
    }
  }
}

medium

A. Initialize dist with 0 instead of usize::MAX

B. Use VecDeque instead of BinaryHeap

C. Remove the if cost > dist[u] check

D. Change heap to store (Reverse<usize>, usize) to get min-heap behavior

Solution

1. Step 1: Understand Rust's BinaryHeap behavior

   Rust's BinaryHeap is a max-heap by default, but Dijkstra needs a min-heap to get the smallest cost first.

2. Step 2: Fix heap to behave as min-heap

   Use std::cmp::Reverse wrapper around cost to invert ordering, so smallest cost is popped first.

3. Final Answer:

   Change heap to store (Reverse<usize>, usize) to get min-heap behavior -> Option D

4. Quick Check:

   BinaryHeap is max-heap by default, use Reverse for min-heap [OK]

Hint: Use Reverse wrapper for min-heap in Rust BinaryHeap [OK]

Common Mistakes:

• Ignoring heap ordering and getting wrong shortest paths
• Initializing distances incorrectly
• Removing important cost check causing wrong updates

5. Given a weighted graph with vertices 0 to 4 and edges:

0 -> 1 (2), 0 -> 2 (4),
1 -> 2 (1), 1 -> 3 (7),
2 -> 4 (3), 3 -> 4 (1)

What is the shortest path distance from vertex 0 to vertex 4 using Dijkstra's Algorithm?

hard

A. 6

B. 7

C. 8

D. 10

Solution

1. Step 1: Calculate tentative distances from vertex 0

   Start: dist[0]=0, others ∞. From 0: dist[1]=2, dist[2]=4.

2. Step 2: Update distances via vertex 1 and 2

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

3. Step 3: Update distance via vertex 3

   From 3: dist[4]=min(6, 9+1=10)=6 (no change).

4. Final Answer:

   6 -> Option A

5. Quick Check:

   Shortest distance 0->4 = 6 [OK]

Hint: Add edge weights along shortest path, pick minimum sum [OK]

Common Mistakes:

• Not updating dist[2] via vertex 1 to 3
• Ignoring shorter path through vertex 2
• Adding edges incorrectly or missing updates