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.