Dijkstra's algorithm in Data Structures Theory - Step-by-Step Execution

Concept Flow - Dijkstra's algorithm

Start at source node

↓

Initialize distances: source=0, others=∞

↓

Mark all nodes unvisited

↓

Select unvisited node with smallest distance

↓

For each neighbor of selected node

↓

Calculate new distance via selected node

↓

If new distance < current distance, update it

↓

Mark selected node as visited

↓

Repeat until all nodes visited or smallest distance is ∞

↓

End: shortest distances found

Dijkstra's algorithm finds the shortest path from a start node to all others by repeatedly selecting the closest unvisited node and updating distances.

Execution Sample

Data Structures Theory

Graph:
A--1--B--2--C
|     |
4     3
|     |
D-----E

Start: A

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

Analysis Table

Step	Current Node	Distances	Visited Nodes	Action	Notes
1	A	{"A":0, "B":∞, "C":∞, "D":∞, "E":∞}	[]	Initialize distances and start at A	Set distance A=0, others ∞
2	A	{"A":0, "B":1, "C":∞, "D":4, "E":∞}	[]	Update neighbors B and D	B=1 via A, D=4 via A
3	A	{"A":0, "B":1, "C":∞, "D":4, "E":∞}	['A']	Mark A visited	A done
4	B	{"A":0, "B":1, "C":3, "D":4, "E":4}	['A']	Update neighbors C and E	C=3 via B, E=4 via B
5	B	{"A":0, "B":1, "C":3, "D":4, "E":4}	['A', 'B']	Mark B visited	B done
6	C	{"A":0, "B":1, "C":3, "D":4, "E":4}	['A', 'B']	No neighbors to update	C neighbors visited or no shorter path
7	C	{"A":0, "B":1, "C":3, "D":4, "E":4}	['A', 'B', 'C']	Mark C visited	C done
8	D	{"A":0, "B":1, "C":3, "D":4, "E":4}	['A', 'B', 'C']	Update neighbor E	E current=4, new via D=8 (no update)
9	D	{"A":0, "B":1, "C":3, "D":4, "E":4}	['A', 'B', 'C', 'D']	Mark D visited	D done
10	E	{"A":0, "B":1, "C":3, "D":4, "E":4}	['A', 'B', 'C', 'D']	No neighbors to update	All neighbors visited or no shorter path
11	E	{"A":0, "B":1, "C":3, "D":4, "E":4}	['A', 'B', 'C', 'D', 'E']	Mark E visited	E done
12	-	{"A":0, "B":1, "C":3, "D":4, "E":4}	['A', 'B', 'C', 'D', 'E']	All nodes visited	Algorithm ends

💡 All nodes visited; shortest distances finalized

State Tracker

Variable	Start	After Step 2	After Step 4	After Step 8	Final
Distances	{"A":0, "B":∞, "C":∞, "D":∞, "E":∞}	{"A":0, "B":1, "C":∞, "D":4, "E":∞}	{"A":0, "B":1, "C":3, "D":4, "E":4}	{"A":0, "B":1, "C":3, "D":4, "E":4}	{"A":0, "B":1, "C":3, "D":4, "E":4}
Visited Nodes	[]	[]	["A", "B"]	["A", "B", "C", "D"]	["A", "B", "C", "D", "E"]
Current Node	A	B	C	D	E

Key Insights - 3 Insights

Why do we update the distance to a neighbor only if the new distance is smaller?

Because Dijkstra's algorithm always keeps the shortest known distance. Updating only when the new path is shorter ensures we find the minimum distance. See execution_table rows 2 and 4 where distances are updated only if smaller.

Why do we mark nodes as visited and never revisit them?

Once a node is visited, its shortest distance is finalized. Revisiting could cause incorrect updates. This is shown in execution_table rows 3, 5, 7, 9, and 11 where nodes are marked visited and not reconsidered.

What happens if a node is unreachable from the source?

Its distance remains infinity (∞) because no path exists. The algorithm stops when all reachable nodes are visited. This is implied in the exit condition in execution_table row 12.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the distance to node C?

A ∞

B 3

C 1

D 4

💡 Hint

Check the Distances column in row with Step 4.

At which step is node D marked as visited?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look at the Visited Nodes column to see when D appears.

If the edge from B to E had weight 1 instead of 3, how would the distance to E change after step 4?

A It would be 2

B It would remain 4

C It would be 3

D It would be ∞

💡 Hint

Calculate distance from A to E via B: A->B=1 plus B->E=1 equals 2.

Concept Snapshot

Dijkstra's algorithm finds shortest paths from a start node to all others.
Initialize distances (start=0, others=∞).
Repeatedly pick unvisited node with smallest distance.
Update neighbors' distances if shorter path found.
Mark nodes visited to finalize distances.
Stops when all nodes visited or unreachable.

Full Transcript

Dijkstra's algorithm starts at a source node, setting its distance to zero and all others to infinity. It keeps track of visited nodes and distances. At each step, it selects the unvisited node with the smallest current distance. It then updates the distances to its neighbors if a shorter path is found through this node. After updating, it marks the current node as visited, meaning its shortest distance is finalized. This process repeats until all nodes are visited or no reachable nodes remain. The final distances represent the shortest paths from the source to every other node in the graph.