Dijkstra's Algorithm Single Source Shortest Path in DSA Rust - Execution Trace

Concept Flow - Dijkstra's Algorithm Single Source Shortest Path

Start: Initialize distances

↓

Set source distance = 0

↓

Add all nodes to unvisited set

↓

While unvisited not empty

↓

Select node with smallest distance

↓

For each neighbor

↓

Calculate new distance

↓

If new distance < known distance

↓

Update distance and predecessor

↓

Mark current node visited

↓

Repeat until all visited

↓

Shortest paths found

Dijkstra's algorithm starts with all nodes at infinite distance except the source. It repeatedly picks the closest unvisited node, updates neighbors' distances, and marks nodes visited until all shortest paths are found.

Execution Sample

DSA Rust

graph = {
  'A': [('B', 1), ('C', 4)],
  'B': [('C', 2), ('D', 5)],
  'C': [('D', 1)],
  'D': []
}
dijkstra('A')

Find shortest paths from node A to all others in a weighted graph.

Execution Table

Step	Operation	Current Node	Distances	Unvisited Set	Visual State
1	Initialize distances and unvisited	None	{"A":0, "B":∞, "C":∞, "D":∞}	[A, B, C, D]	A(0) B(∞) C(∞) D(∞)
2	Select node with smallest distance	A	{"A":0, "B":∞, "C":∞, "D":∞}	[A, B, C, D]	A(0) B(∞) C(∞) D(∞)
3	Update neighbors of A	A	{"A":0, "B":1, "C":4, "D":∞}	[A, B, C, D]	A(0) B(1) C(4) D(∞)
4	Mark A visited	A	{"A":0, "B":1, "C":4, "D":∞}	[B, C, D]	A(0) B(1) C(4) D(∞)
5	Select node with smallest distance	B	{"A":0, "B":1, "C":4, "D":∞}	[B, C, D]	A(0) B(1) C(4) D(∞)
6	Update neighbors of B	B	{"A":0, "B":1, "C":3, "D":6}	[B, C, D]	A(0) B(1) C(3) D(6)
7	Mark B visited	B	{"A":0, "B":1, "C":3, "D":6}	[C, D]	A(0) B(1) C(3) D(6)
8	Select node with smallest distance	C	{"A":0, "B":1, "C":3, "D":6}	[C, D]	A(0) B(1) C(3) D(6)
9	Update neighbors of C	C	{"A":0, "B":1, "C":3, "D":4}	[C, D]	A(0) B(1) C(3) D(4)
10	Mark C visited	C	{"A":0, "B":1, "C":3, "D":4}	[D]	A(0) B(1) C(3) D(4)
11	Select node with smallest distance	D	{"A":0, "B":1, "C":3, "D":4}	[D]	A(0) B(1) C(3) D(4)
12	No neighbors to update	D	{"A":0, "B":1, "C":3, "D":4}	[D]	A(0) B(1) C(3) D(4)
13	Mark D visited	D	{"A":0, "B":1, "C":3, "D":4}	[]	A(0) B(1) C(3) D(4)

💡 All nodes visited, shortest distances finalized

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
Distances	{"A":∞, "B":∞, "C":∞, "D":∞}	{"A":0, "B":∞, "C":∞, "D":∞}	{"A":0, "B":1, "C":4, "D":∞}	{"A":0, "B":1, "C":4, "D":∞}	{"A":0, "B":1, "C":3, "D":6}	{"A":0, "B":1, "C":3, "D":4}	{"A":0, "B":1, "C":3, "D":4}
Unvisited Set	[A, B, C, D]	[A, B, C, D]	[B, C, D]	[B, C, D]	[C, D]	[C, D]	[]
Current Node	None	A	A	B	B	C	D

Key Moments - 3 Insights

Why do we update distances only if the new distance is smaller?

Because Dijkstra's algorithm always keeps the shortest known distance. Updating only when the new distance is smaller ensures we don't overwrite a better path with a longer one. See steps 3 and 6 in the execution_table where distances are updated only when smaller.

Why do we mark nodes as visited after processing?

Marking nodes visited means their shortest distance is finalized and won't change. This prevents revisiting and infinite loops. Look at steps 4, 7, 10, and 13 where nodes are marked visited after updating neighbors.

What happens if a node has no neighbors?

If a node has no neighbors, no distances are updated in that step. The algorithm simply marks it visited and moves on. Step 12 shows node D with no neighbors, so no updates occur.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the distance to node C?

A 4

B 3

C ∞

D 1

💡 Hint

Check the Distances column at step 6 in the execution_table.

At which step does node C get marked as visited?

A Step 9

B Step 10

C Step 11

D Step 7

💡 Hint

Look for 'Mark C visited' in the Operation column of the execution_table.

If the edge from B to D had weight 1 instead of 5, what would be the distance to D after step 7?

A 4

B 6

C 2

D ∞

💡 Hint

Consider how updating neighbors works in step 6 and the new edge weight.

Concept Snapshot

Dijkstra's Algorithm:
- Initialize all distances to ∞ except source = 0
- Use a set of unvisited nodes
- Pick unvisited node with smallest distance
- Update neighbors' distances if shorter path found
- Mark node visited after processing
- Repeat until all nodes visited
- Result: shortest distances from source to all nodes

Full Transcript

Dijkstra's algorithm finds the shortest path from one starting point to all other points in a weighted graph. It begins by setting all distances to infinity except the start node, which is zero. It keeps track of nodes not yet visited. Each step, it picks the closest unvisited node, updates the distances to its neighbors if a shorter path is found, then marks the node as visited. This repeats until all nodes are visited. The final distances show the shortest path lengths from the start to every node.

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