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

Concept Flow - Dijkstra's Algorithm Single Source Shortest Path

Start: Initialize distances

↓

Set source distance = 0

↓

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

The algorithm starts by setting distances, then repeatedly picks the closest unvisited node, updates neighbors' distances, and continues until all shortest paths are found.

Execution Sample

DSA Typescript

const graph = {
  A: {B: 1, C: 4},
  B: {C: 2, D: 5},
  C: {D: 1},
  D: {}
};
// Find shortest paths from A

This code finds shortest paths from node A to all others in a weighted graph.

Execution Table

Step	Operation	Current Node	Distances	Priority Queue	Visual State
1	Initialize distances and queue	None	{"A":0,"B":Infinity,"C":Infinity,"D":Infinity}	[A:0]	Graph nodes: A, B, C, D; Distances set; Queue contains A
2	Extract node with smallest distance	A	{"A":0,"B":Infinity,"C":Infinity,"D":Infinity}	[]	Visiting A; Queue empty after extraction
3	Update neighbors of A	A	{"A":0,"B":1,"C":4,"D":Infinity}	[B:1, C:4]	Updated B and C distances; Queue updated with B and C
4	Extract node with smallest distance	B	{"A":0,"B":1,"C":4,"D":Infinity}	[C:4]	Visiting B; Queue has C
5	Update neighbors of B	B	{"A":0,"B":1,"C":3,"D":6}	[C:3, D:6, C:4]	Updated C and D distances; Queue updated with C(3) and D(6)
6	Extract node with smallest distance	C	{"A":0,"B":1,"C":3,"D":6}	[C:4, D:6]	Visiting C; Queue has C(4) and D(6)
7	Update neighbors of C	C	{"A":0,"B":1,"C":3,"D":4}	[D:4, D:6, C:4]	Updated D distance; Queue updated with D(4)
8	Extract node with smallest distance	D	{"A":0,"B":1,"C":3,"D":4}	[D:6, C:4]	Visiting D; Queue has D(6) and C(4)
9	D has no neighbors to update	D	{"A":0,"B":1,"C":3,"D":4}	[D:6, C:4]	No updates; Queue unchanged
10	Extract node with smallest distance	C	{"A":0,"B":1,"C":3,"D":4}	[D:6]	Visiting C again (from previous queue entry); no updates
11	Extract node with smallest distance	D	{"A":0,"B":1,"C":3,"D":4}	[]	Visiting D again; no updates; Queue empty
12	Algorithm ends	None	{"A":0,"B":1,"C":3,"D":4}	[]	All shortest distances finalized

💡 Priority queue is empty; all nodes processed with shortest distances found

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
Distances	{"A":0,"B":Infinity,"C":Infinity,"D":Infinity}	{"A":0,"B":1,"C":4,"D":Infinity}	{"A":0,"B":1,"C":3,"D":6}	{"A":0,"B":1,"C":3,"D":4}	{"A":0,"B":1,"C":3,"D":4}
Priority Queue	[A:0]	[B:1, C:4]	[C:3, D:6, C:4]	[D:4, D:6, C:4]	[]
Current Node	None	A	B	C	None

Key Moments - 3 Insights

Why does the priority queue sometimes contain duplicate nodes with different distances?

Because when a shorter path to a node is found, it is added again to the queue without removing the old entry. The algorithm ignores outdated entries when they come out of the queue, as shown in steps 10 and 11.

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

Because Dijkstra's algorithm finds the shortest path. Updating only when the new distance is smaller ensures we keep the shortest known distance, as seen in step 5 when C's distance is updated from 4 to 3.

What happens when a node has no neighbors?

No updates occur, and the algorithm simply moves on. For example, node D in step 9 has no neighbors, so no changes happen.

Visual Quiz - 3 Questions

Look at the execution table at step 5. What is the updated distance for node C?

A 3

B 4

C 6

D 1

💡 Hint

Check the 'Distances' column at step 5 in the execution table.

At which step does the priority queue become empty, ending the algorithm?

A Step 9

B Step 11

C Step 12

D Step 10

💡 Hint

Look at the 'Priority Queue' column and the 'Exit Note' in the execution table.

If the edge from B to D had weight 2 instead of 5, how would the distance to D change after step 5?

A It would be 3

B It would be 6

C It would be 2

D It would remain Infinity

💡 Hint

Calculate new distance: distance to B (1) + edge weight (2) = 3, compare with current D distance.

Concept Snapshot

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

Full Transcript

Dijkstra's Algorithm starts by setting all node distances to infinity except the source node, which is zero. It uses a priority queue to always pick the node with the smallest known distance. For each picked node, it checks all neighbors and updates their distances if a shorter path is found. Updated neighbors are added to the queue. Sometimes the queue contains duplicates for the same node with different distances; outdated entries are ignored when processed. The algorithm ends when the queue is empty, and all shortest distances are finalized.