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

Concept Flow - Dijkstra's Algorithm Single Source Shortest Path

Start with source node

↓

Initialize distances: source=0, others=∞

↓

Create priority queue with source

↓

While queue not empty

↓

Extract node with smallest distance

↓

For each neighbor

↓

Calculate new distance

↓

If new distance < known distance

↓

Update distance

↓

Add neighbor to queue

↓

Repeat until queue empty

↓

Distances finalized

Start from the source node, update shortest distances to neighbors using a priority queue until all nodes have shortest paths.

Execution Sample

DSA C++

graph = {
 0: [(1, 4), (2, 1)],
 1: [(3, 1)],
 2: [(1, 2), (3, 5)],
 3: []
}
dijkstra(0)

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

Execution Table

Step	Operation	Current Node	Distances	Priority Queue	Visual State
1	Initialize distances and queue	None	{0:0,1:∞,2:∞,3:∞}	[ (0,0) ]	0(0) → 1(∞) → 2(∞) → 3(∞)
2	Extract min distance node	0	{0:0,1:∞,2:∞,3:∞}	[]	0(0) → 1(∞) → 2(∞) → 3(∞)
3	Check neighbors of 0	0	{0:0,1:4,2:1,3:∞}	[ (2,1), (1,4) ]	0(0) → 1(4) → 2(1) → 3(∞)
4	Extract min distance node	2	{0:0,1:4,2:1,3:∞}	[ (1,4) ]	0(0) → 1(4) → 2(1) → 3(∞)
5	Check neighbors of 2	2	{0:0,1:3,2:1,3:6}	[ (1,3), (1,4) ]	0(0) → 1(3) → 2(1) → 3(6)
6	Extract min distance node	1	{0:0,1:3,2:1,3:6}	[ (3,4), (1,4) ]	0(0) → 1(3) → 2(1) → 3(6)
7	Check neighbors of 1	1	{0:0,1:3,2:1,3:4}	[ (3,4), (1,4) ]	0(0) → 1(3) → 2(1) → 3(4)
8	Extract min distance node	3	{0:0,1:3,2:1,3:4}	[ (1,4) ]	0(0) → 1(3) → 2(1) → 3(4)
9	Node 3 has no neighbors	3	{0:0,1:3,2:1,3:4}	[ (1,4) ]	0(0) → 1(3) → 2(1) → 3(4)
10	Extract min distance node	1	{0:0,1:3,2:1,3:4}	[]	0(0) → 1(3) → 2(1) → 3(4)
11	No update needed for neighbors	1	{0:0,1:3,2:1,3:4}	[]	0(0) → 1(3) → 2(1) → 3(4)
12	Priority queue empty, done	None	{0:0,1:3,2:1,3:4}	[]	0(0) → 1(3) → 2(1) → 3(4)

💡 Priority queue empty, all shortest distances finalized

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
Distances	{0:∞,1:∞,2:∞,3:∞}	{0:0,1:4,2:1,3:∞}	{0:0,1:3,2:1,3:6}	{0:0,1:3,2:1,3:4}	{0:0,1:3,2:1,3:4}
Priority Queue	[(0,0)]	[(2,1),(1,4)]	[(1,3),(1,4)]	[(3,4),(1,4)]	[]
Current Node	None	0	2	1	None

Key Moments - 3 Insights

Why do we update the distance of node 1 from 4 to 3 at step 5?

At step 5, we find a shorter path to node 1 through node 2 with distance 1 + 2 = 3, which is less than the previous 4. This is shown in execution_table row 5 where distances update.

Why does the priority queue contain duplicate entries for node 1 at steps 5 and 6?

When a shorter distance is found, the new pair is added to the queue without removing old entries. The algorithm ignores outdated entries when extracted, as seen in steps 6 and 10.

Why do we stop when the priority queue is empty at step 12?

When the queue is empty, all nodes have their shortest distances finalized. No more nodes to process means the algorithm is complete, as noted in the exit_note.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the updated distance of node 3?

A ∞

B 4

C 6

D 5

💡 Hint

Check the Distances column at step 5 in execution_table

At which step does the priority queue become empty?

A Step 10

B Step 12

C Step 8

D Step 6

💡 Hint

Look at the Priority Queue column in execution_table rows

If the edge from node 2 to node 3 had weight 1 instead of 5, what would be the distance to node 3 after step 5?

A 2

B 3

C 4

D 5

💡 Hint

Consider the new distance calculation: distance to 2 + edge weight to 3

Concept Snapshot

Dijkstra's Algorithm finds shortest paths from one node to all others.
Initialize distances with source=0 and others=∞.
Use a priority queue to pick the closest unvisited node.
Update neighbors' distances if shorter paths found.
Repeat until all nodes processed.
Result: shortest distance from source to every node.

Full Transcript

Dijkstra's Algorithm starts by setting the source node distance to zero and all others to infinity. It uses a priority queue to always pick the node with the smallest known distance. For each extracted node, it checks neighbors and updates their distances if a shorter path is found. Updated neighbors are added to the queue. This process repeats until the queue is empty, meaning all shortest paths are finalized. The execution table shows step-by-step how distances and the queue change. Key moments clarify why distances update, why duplicates appear in the queue, and when the algorithm ends. The visual quiz tests understanding of distance updates, queue emptiness, and impact of edge weight changes.

Practice

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

easy

A. To sort vertices in topological order

B. To find the maximum flow in a network

C. To detect cycles in a graph

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

Solution

1. Step 1: Understand the algorithm's goal

   Dijkstra's Algorithm is designed to find the shortest distances from one starting point (source) to every other point in a graph with non-negative edge weights.

2. Step 2: Compare with other graph algorithms

   Other algorithms like max flow or cycle detection serve different purposes, so they do not match Dijkstra's goal.

3. Final Answer:

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

4. Quick Check:

   Dijkstra's Algorithm = shortest paths from source [OK]

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

Common Mistakes:

• Confusing Dijkstra with algorithms for max flow
• Thinking it detects cycles
• Assuming it sorts vertices

2. Which of the following is the correct way to initialize the distance array in Dijkstra's Algorithm in C++?

easy

A. vector<int> dist(n, -1); dist[source] = 0;

B. vector<int> dist(n, INT_MAX); dist[source] = 0;

C. vector<int> dist(n, 0); dist[source] = INT_MAX;

D. vector<int> dist(n); dist[source] = 0;

Solution

1. Step 1: Understand distance initialization

   Distances to all nodes except the source should start as infinity (or a very large number) to represent unknown distance.

2. Step 2: Check each option

   vector<int> dist(n, INT_MAX); dist[source] = 0; correctly sets all distances to INT_MAX and source distance to 0. Others either set wrong initial values or leave uninitialized.

3. Final Answer:

   vector<int> dist(n, INT_MAX); dist[source] = 0; -> Option B

4. Quick Check:

   Distance array initialized with INT_MAX except source = 0 [OK]

Hint: Initialize all distances to max except source zero [OK]

Common Mistakes:

• Setting all distances to zero initially
• Not setting source distance to zero
• Leaving distance array uninitialized

3. Consider the following graph edges and weights:

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

If we run Dijkstra's Algorithm from source vertex 0, what is the shortest distance array after completion?

medium

A. [0, 3, 1, 4]

B. [0, 4, 1, 6]

C. [0, 2, 1, 3]

D. [0, 5, 1, 7]

Solution

1. Step 1: Initialize distances

   Start with dist = [0, INF, INF, INF]. Source 0 distance is 0.

2. Step 2: Relax edges step-by-step

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

3. Final Answer:

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

4. Quick Check:

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

Hint: Update distances by relaxing edges with minimum sums [OK]

Common Mistakes:

• Not updating distance to vertex 1 via vertex 2
• Incorrectly summing edge weights
• Ignoring better paths found later

4. The following C++ code snippet for Dijkstra's Algorithm has a bug. What is the error?

vector<int> dist(n, INT_MAX);
dist[source] = 0;
priority_queue> pq;
pq.push({0, source});
while(!pq.empty()) {
  int u = pq.top().second;
  int d = pq.top().first;
  pq.pop();
  if(d > dist[u]) continue;
  for(auto &edge : graph[u]) {
    int v = edge.first;
    int w = edge.second;
    if(dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
      pq.push({dist[v], v});
    }
  }
}

medium

A. priority_queue is max-heap by default (needs negative distances or greater comparator)

B. Distance array is not initialized correctly

C. The graph adjacency list is not iterated properly

D. The source distance is not set to zero

Solution

1. Step 1: Check priority queue usage

   In C++, priority_queue by default is max-heap. To get min-heap behavior for distances, distances should be pushed as negative or use greater comparator.

2. Step 2: Identify the bug

   The code pushes distances as positive values, so the smallest distance won't be on top, causing incorrect behavior.

3. Final Answer:

   priority_queue is max-heap by default (needs negative distances or greater comparator) -> Option A

4. Quick Check:

   Use negative distances or min-heap for correct priority queue [OK]

Hint: Use negative distances or min-heap to get smallest distance first [OK]

Common Mistakes:

• Ignoring priority queue ordering behavior
• Not setting source distance to zero
• Incorrect graph iteration

5. You have a weighted graph with 5 vertices and edges:

0->1(10), 0->4(5), 1->2(1), 2->3(4), 4->1(3), 4->2(9), 4->3(2), 3->0(7)

Using Dijkstra's Algorithm from source 0, what is the shortest distance to vertex 3?

hard

A. 13

B. 15

C. 7

D. 18

Solution

1. Step 1: Initialize distances

   dist = [0, INF, INF, INF, INF]. Source 0 distance is 0.

2. Step 2: Relax edges step-by-step

   From 0: dist[1]=10, dist[4]=5. From 4: dist[1]=min(10,5+3=8)=8, dist[2]=min(INF,5+9=14)=14, dist[3]=min(INF,5+2=7)=7. From 1: dist[2]=min(14,8+1=9)=9. From 2: dist[3]=min(7,9+4=13)=7.

3. Step 3: Final shortest distance to vertex 3

   The shortest distance to vertex 3 is 7.

4. Final Answer:

   7 -> Option C

5. Quick Check:

   Shortest distance to vertex 3 = 7 [OK]

Hint: Relax edges in order, update distances with minimum sums [OK]

Common Mistakes:

• Not updating distances via vertex 4
• Ignoring better paths through intermediate vertices
• Confusing edge weights