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

Concept Flow - Dijkstra's Algorithm Single Source Shortest Path

Start: Initialize distances

↓

Pick unvisited node with smallest distance

↓

Update distances of neighbors

↓

Mark node as visited

↓

Are all nodes visited?

No→Repeat pick node

Yes↓

Done

Start with all distances infinite except source. Pick closest unvisited node, update neighbors, mark visited, repeat until all nodes processed.

Execution Sample

DSA C

int dist[V];
bool visited[V];
for (int i = 0; i < V; i++) {
  dist[i] = INT_MAX; visited[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V-1; count++) {
  int u = minDistance(dist, visited);
  visited[u] = true;
  for (int v = 0; v < V; v++) {
    if (!visited[v] && graph[u][v] != 0 && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
      dist[v] = dist[u] + graph[u][v];
    }
  }
}

This code finds shortest paths from source to all nodes using Dijkstra's algorithm on a graph represented by adjacency matrix.

Execution Table

Step	Operation	Current Node (u)	Distances Array	Visited Set	Visual State
1	Initialize distances and visited	None	[0, ∞, ∞, ∞, ∞]	{}	Distances: src=0, others ∞; Visited: none
2	Pick node with min dist	0	[0, ∞, ∞, ∞, ∞]	{}	Node 0 selected (distance 0)
3	Update neighbors of 0	0	[0, 10, 3, ∞, ∞]	{}	Distances updated: node1=10, node2=3
4	Mark node 0 visited	0	[0, 10, 3, ∞, ∞]	{0}	Visited nodes: 0
5	Pick node with min dist	2	[0, 10, 3, ∞, ∞]	{0}	Node 2 selected (distance 3)
6	Update neighbors of 2	2	[0, 10, 3, 6, ∞]	{0}	Distance to node3 updated to 6
7	Mark node 2 visited	2	[0, 10, 3, 6, ∞]	{0,2}	Visited nodes: 0,2
8	Pick node with min dist	3	[0, 10, 3, 6, ∞]	{0,2}	Node 3 selected (distance 6)
9	Update neighbors of 3	3	[0, 10, 3, 6, 9]	{0,2}	Distance to node4 updated to 9
10	Mark node 3 visited	3	[0, 10, 3, 6, 9]	{0,2,3}	Visited nodes: 0,2,3
11	Pick node with min dist	4	[0, 10, 3, 6, 9]	{0,2,3}	Node 4 selected (distance 9)
12	Update neighbors of 4	4	[0, 10, 3, 6, 9]	{0,2,3}	No distance updates
13	Mark node 4 visited	4	[0, 10, 3, 6, 9]	{0,2,3,4}	Visited nodes: 0,2,3,4
14	Pick node with min dist	1	[0, 10, 3, 6, 9]	{0,2,3,4}	Node 1 selected (distance 10)
15	Update neighbors of 1	1	[0, 10, 3, 6, 9]	{0,2,3,4}	No distance updates
16	Mark node 1 visited	1	[0, 10, 3, 6, 9]	{0,1,2,3,4}	All nodes visited, done

💡 All nodes visited, shortest distances finalized

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 12	After Step 15	Final
dist	[0, ∞, ∞, ∞, ∞]	[0, 10, 3, ∞, ∞]	[0, 10, 3, 6, ∞]	[0, 10, 3, 6, 9]	[0, 10, 3, 6, 9]	[0, 10, 3, 6, 9]	[0, 10, 3, 6, 9]
visited	{}	{}	{0}	{0,2}	{0,2,3}	{0,2,3,4}	{0,1,2,3,4}
current node (u)	None	0	2	3	4	1	None

Key Moments - 3 Insights

Why do we pick the unvisited node with the smallest distance each time?

Because that node's shortest path is finalized; picking it ensures we update neighbors correctly without missing shorter paths. See execution_table rows 2,5,8,11,14 where nodes with smallest distances are chosen.

Why do distances only update if dist[u] + graph[u][v] < dist[v]?

This condition ensures we only update if we found a shorter path to node v through u. Refer to execution_table rows 3,6,9 where distances get updated only when shorter.

What happens if a node is already visited?

We skip it to avoid reprocessing and infinite loops. The visited set in execution_table rows shows nodes once visited are not picked again.

Visual Quiz - 3 Questions

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

A 6

B ∞

C 3

D 10

💡 Hint

Check the Distances Array column at step 6 in execution_table

At which step does node 1 get marked as visited?

A Step 14

B Step 10

C Step 16

D Step 12

💡 Hint

Look at the Visited Set and Operation columns in execution_table

If the edge from node 2 to node 3 had weight 10 instead of 3, how would the distance to node 3 change after step 6?

A It would become 10

B It would become 13

C It would remain ∞

D It would become 6

💡 Hint

Distance to node 3 is dist[2] + edge weight; see update logic in execution_table step 6

Concept Snapshot

Dijkstra's Algorithm finds shortest paths from one source node.
Initialize all distances to infinity except source (0).
Pick unvisited node with smallest distance.
Update neighbors' distances if shorter path found.
Mark node visited and repeat until all visited.
Result: shortest distance array from source.

Full Transcript

Dijkstra's Algorithm starts by setting all node distances to infinity except the source node which is zero. It repeatedly picks the unvisited node with the smallest known distance, then updates the distances of its neighbors if a shorter path is found through this node. After updating neighbors, it marks the current node as visited so it won't be processed again. This process continues until all nodes are visited, resulting in the shortest distances from the source to every other node. The execution table shows each step with the current node, distances array, visited nodes, and the visual state of the graph. Key moments clarify why we pick the smallest distance node, why we update distances only when shorter, and why visited nodes are skipped. The visual quiz tests understanding of distance updates, visited steps, and effects of edge weight changes.

Practice

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

easy

A. To sort the vertices of a graph topologically

B. To find the minimum spanning tree of a graph

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 goal of Dijkstra's Algorithm

   Dijkstra's Algorithm is designed to find the shortest distance 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

   Minimum spanning tree algorithms find a tree connecting all vertices with minimum total edge weight, cycle detection finds loops, and topological sort orders vertices in directed acyclic graphs. These are different goals.

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: Dijkstra finds shortest paths from one start point [OK]

Common Mistakes:

• Confusing with minimum spanning tree algorithms
• 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. int dist[V]; for(int i=0; i

B. int dist[V] = {INT_MAX};

C. int dist[V] = {0};

D. int dist[V] = NULL;

Solution

1. Step 1: Understand distance initialization

   Distances should start as infinity (or a very large number) except the source vertex, to represent unknown shortest paths.

2. Step 2: Check each option

   int dist[V] = {0}; initializes all distances to 0, which is incorrect. int dist[V]; for(int i=0; i

3. Final Answer:

   int dist[V]; for(int i=0; i -> Option A

4. Quick Check:

   Initialize distances to INT_MAX with loop [OK]

Hint: Use loop to set all distances to INT_MAX [OK]

Common Mistakes:

• Using {INT_MAX} initializes only first element
• Setting all distances to 0
• Assigning NULL to int array

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

int graph[4][4] = {
  {0, 1, 4, 0},
  {1, 0, 2, 6},
  {4, 2, 0, 3},
  {0, 6, 3, 0}
};

medium

A. [0, 1, 4, 7]

B. [0, 1, 3, 5]

C. [0, 1, 3, 6]

D. [0, 2, 4, 6]

Solution

1. Step 1: Initialize distances and start from vertex 0

   Distances: dist[0]=0, dist[1]=∞, dist[2]=∞, dist[3]=∞. Update neighbors of 0: dist[1]=1, dist[2]=4.

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

   Pick vertex 1 (dist=1). Update dist[2] = min(4, 1+2=3) = 3, dist[3] = min(∞, 1+6=7) = 7. Next pick vertex 2 (dist=3). Update dist[3] = min(7, 3+3=6) = 6. Finally pick vertex 3 (dist=6).

3. Final Answer:

   [0, 1, 3, 6] -> Option C

4. Quick Check:

   Distances after relaxation = [0,1,3,6] [OK]

Hint: Relax edges stepwise, pick smallest distance vertex next [OK]

Common Mistakes:

• Not updating distances after relaxation
• Choosing wrong next vertex
• Ignoring shorter paths through intermediate vertices

4. Identify the error in the following snippet of Dijkstra's Algorithm in C:

for (int count = 0; count < V-1; count++) {
  int u = minDistance(dist, sptSet);
  sptSet[u] = 1;
  for (int v = 0; v < V; v++) {
    if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
      dist[v] = dist[u] + graph[u][v];
    }
  }
}

medium

A. The loop should run from 1 to V instead of 0 to V-1

B. The condition 'graph[u][v]' should be 'graph[u][v] != 0' to check edge existence

C. The sptSet array should be initialized with 1 instead of 0

D. The dist[u] check should be 'dist[u] == INT_MAX' instead of '!='

Solution

1. Step 1: Analyze edge existence condition

   The condition 'graph[u][v]' relies on implicit truthiness of non-zero values. In C, this works but is less clear. Using 'graph[u][v] != 0' explicitly checks for edge presence and improves readability.

2. Step 2: Check other conditions

   Loop range from 0 to V-1 is correct for V vertices. sptSet should start with 0 (false). The dist[u] check must be '!= INT_MAX' to ensure u is reachable before relaxing edges.

3. Final Answer:

   The condition 'graph[u][v]' should be 'graph[u][v] != 0' to check edge existence -> Option B

4. Quick Check:

   Explicit edge check improves clarity [OK]

Hint: Use explicit '!= 0' to check edges in adjacency matrix [OK]

Common Mistakes:

• Assuming loop range is wrong
• Initializing sptSet incorrectly
• Reversing dist[u] check logic

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

0-1: 7, 0-2: 9, 0-5: 14, 1-2: 10, 1-3: 15, 2-3: 11, 2-5: 2, 3-4: 6, 4-5: 9

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

hard

A. 20

B. 26

C. 21

D. 19

Solution

1. Step 1: Initialize distances and start from vertex 0

   dist[0]=0, others = ∞. Update neighbors: dist[1]=7, dist[2]=9, dist[5]=14.

2. Step 2: Pick vertex with smallest dist and update neighbors

   Pick 1 (7): update dist[3] = min(∞, 7+15=22) = 22. Pick 2 (9): update dist[3] = min(22, 9+11=20) = 20, dist[5] = min(14, 9+2=11) = 11. Pick 5 (11): update dist[4] = min(∞, 11+9=20) = 20. Pick 3 (20): update dist[4] = min(20, 20+6=26) = 20. Pick 4 (20).

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Shortest path to 4 = 20 [OK]

Hint: Relax edges carefully, update shortest distances stepwise [OK]

Common Mistakes:

• Not updating dist[5] to smaller value
• Ignoring shorter path through vertex 2
• Adding edges incorrectly