Dijkstra's Algorithm Single Source Shortest Path in DSA Rust - Build from Scratch

Dijkstra's Algorithm Single Source Shortest Path

📖 Scenario: You are working on a navigation system that finds the shortest path from one city to all other cities on a map. The map is represented as a graph where cities are nodes and roads are edges with distances.

🎯 Goal: Build a Rust program that uses Dijkstra's algorithm to find the shortest distance from a starting city to all other cities in the graph.

📋 What You'll Learn

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

Set up a distance vector to track shortest distances

Implement Dijkstra's algorithm using a priority queue

Print the shortest distances from the start city to all others

💡 Why This Matters

🌍 Real World

Navigation apps and GPS devices use Dijkstra's algorithm to find the shortest route between locations.

💼 Career

Understanding shortest path algorithms is important for software engineers working in mapping, logistics, network routing, and game development.

1

Create the graph as an adjacency list

Create a variable called graph as a vector of vectors of tuples. The graph should have 5 nodes (0 to 4) with these edges and weights:
0 -> (1, 10), (3, 5)
1 -> (2, 1), (3, 2)
2 -> (4, 4)
3 -> (1, 3), (2, 9), (4, 2)
4 -> (0, 7), (2, 6)

DSA Rust

# Your code here to create the graph variable with the exact edges and weights

Hint

Use a Vec> where each inner vector holds tuples of (neighbor, weight).

2

Set up the distance vector and starting point

Create a mutable vector called distances of type Vec with length 5, initialized with usize::MAX. Then set the distance for the start node 0 to 0.

DSA Rust

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

// Your code here to create distances vector and set distances[0] = 0

Hint

Use vec![usize::MAX; 5] to create the vector and then assign distances[0] = 0.

3

Implement Dijkstra's algorithm main loop

Use a BinaryHeap as a min-heap by pushing tuples of (distance, node). Initialize it with (0, 0). Then write a while let Some((dist, node)) = heap.pop() loop. Inside the loop, skip if dist > distances[node]. Otherwise, iterate neighbors with for &(neighbor, weight) in &graph[node]. Calculate new distance and update distances[neighbor] and push to heap if smaller.

DSA Rust

use std::collections::BinaryHeap;

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

let mut distances: Vec = vec![usize::MAX; 5];
distances[0] = 0;

// Your code here to implement Dijkstra's algorithm main loop using BinaryHeap

Hint

Use usize::MAX - distance to simulate a min-heap with BinaryHeap because it is a max-heap by default.

4

Print the shortest distances from start node

Use a for loop with i and dist over distances.iter().enumerate(). Print each line as "Distance from 0 to {i} is {dist}" using println!.

DSA Rust

use std::collections::BinaryHeap;

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

let mut distances: Vec = vec![usize::MAX; 5];
distances[0] = 0;

let mut heap = BinaryHeap::new();
heap.push((usize::MAX, 0));

while let Some((dist, node)) = heap.pop() {
    let dist = usize::MAX - dist;
    if dist > distances[node] {
        continue;
    }
    for &(neighbor, weight) in &graph[node] {
        let next_dist = dist + weight;
        if next_dist < distances[neighbor] {
            distances[neighbor] = next_dist;
            heap.push((usize::MAX - next_dist, neighbor));
        }
    }
}

// Your code here to print distances

Hint

Use println!("Distance from 0 to {} is {}", i, dist) inside a for loop over distances.iter().enumerate().

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