Dijkstra's Algorithm Single Source Shortest Path in DSA Rust

Mental Model

Find the shortest path from one starting point to all other points by always choosing the closest unvisited point next.

Analogy: Imagine you are in a city and want to find the shortest way to every other city by always traveling to the nearest city you haven't visited yet.

Start: A graph with nodes and weighted edges.
Example:
  (A)
  / \5
1/   \2
(B)---3--(C)
Weights show travel cost between nodes.

Dry Run Walkthrough

Input: Graph with nodes A, B, C and edges: A-B=1, A-C=2, B-C=3; start at A

Goal: Find shortest distances from A to all nodes

Step 1: Initialize distances: A=0, B=∞, C=∞; mark all unvisited

Distances: A=0, B=∞, C=∞; Unvisited={A,B,C}

Why: Start with source node distance zero and others unknown

Step 2: Visit node A (closest unvisited); update neighbors B and C distances

Distances: A=0, B=1, C=2; Unvisited={B,C}

Why: From A, we can reach B with cost 1 and C with cost 2

Step 3: Visit node B (closest unvisited with distance 1); update neighbor C if shorter path found

Distances: A=0, B=1, C=2; Unvisited={C}

Why: Check if path A->B->C (cost 4) is shorter than current C=2; it is not

Step 4: Visit node C (last unvisited); no neighbors to update

Distances: A=0, B=1, C=2; Unvisited={}

Why: All nodes visited, shortest paths found

Result:

Distances: A=0, B=1, C=2

Annotated Code

DSA Rust

use std::collections::{BinaryHeap, HashMap};
use std::cmp::Ordering;

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

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

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

fn dijkstra(graph: &HashMap<char, Vec<(char, usize)>>, start: char) -> HashMap<char, usize> {
    let mut dist: HashMap<char, usize> = HashMap::new();
    let mut heap = BinaryHeap::new();

    for &node in graph.keys() {
        dist.insert(node, usize::MAX);
    }
    dist.insert(start, 0);
    heap.push(State { cost: 0, position: start });

    while let Some(State { cost, position }) = heap.pop() {
        if cost > *dist.get(&position).unwrap() {
            continue;
        }

        if let Some(neighbors) = graph.get(&position) {
            for &(neighbor, weight) in neighbors {
                let next = State { cost: cost + weight, position: neighbor };

                if next.cost < *dist.get(&neighbor).unwrap_or(&usize::MAX) {
                    dist.insert(neighbor, next.cost);
                    heap.push(next);
                }
            }
        }
    }

    dist
}

fn main() {
    let mut graph: HashMap<char, Vec<(char, usize)>> = HashMap::new();
    graph.insert('A', vec![('B', 1), ('C', 2)]);
    graph.insert('B', vec![('A', 1), ('C', 3)]);
    graph.insert('C', vec![('A', 2), ('B', 3)]);

    let distances = dijkstra(&graph, 'A');

    for node in ['A', 'B', 'C'] {
        let dist = distances.get(&node).unwrap_or(&usize::MAX);
        if *dist == usize::MAX {
            println!("Distance from A to {}: unreachable", node);
        } else {
            println!("Distance from A to {}: {}", node, dist);
        }
    }
}

dist.insert(start, 0);

Set distance to start node as zero

heap.push(State { cost: 0, position: start });

Add start node to priority queue with cost zero

while let Some(State { cost, position }) = heap.pop() {

Process nodes in order of smallest current cost

if cost > *dist.get(&position).unwrap() { continue; }

Skip if we already found a shorter path to this node

for &(neighbor, weight) in neighbors {

Check all neighbors of current node

if next.cost < *dist.get(&neighbor).unwrap_or(&usize::MAX) {

If new path to neighbor is shorter, update distance and queue

Output

Distance from A to A: 0

Distance from A to B: 1

Distance from A to C: 2

Complexity Analysis

Time: O(E log V) because each edge is checked and priority queue operations take log V time

Space: O(V + E) to store graph and distance data

vs Alternative: Better than naive approach of checking all paths which can be exponential; uses priority queue to efficiently pick next closest node

Edge Cases

Graph with unreachable nodes

Distances for unreachable nodes remain usize::MAX and reported as unreachable

DSA Rust

if *dist == usize::MAX { println!("Distance from A to {}: unreachable", node); }

Graph with single node

Distance to itself is zero, no neighbors to update

DSA Rust

dist.insert(start, 0);

Graph with zero-weight edges

Algorithm handles zero weights normally, updating distances if shorter

DSA Rust

if next.cost < *dist.get(&neighbor).unwrap_or(&usize::MAX) {

When to Use This Pattern

When you need shortest paths from one point to many in a weighted graph with no negative edges, reach for Dijkstra's algorithm because it efficiently finds minimum distances using a priority queue.

Common Mistakes

Mistake: Not updating distances when a shorter path is found
Fix: Always check if new path cost is less than current stored distance before updating

Mistake: Using a normal queue instead of a priority queue
Fix: Use a priority queue (min-heap) to always pick the closest unvisited node next

Summary

Finds shortest paths from one start node to all others in a weighted graph without negative edges.

Use when you want minimum travel cost from one point to many points efficiently.

Always pick the closest unvisited node next and update neighbors if shorter paths are found.

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