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.

Practice

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

easy

A. To detect cycles in a graph

B. To find the minimum spanning tree of a graph

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

D. To sort the vertices in topological order

Solution

1. Step 1: Understand the algorithm's goal

   Dijkstra's Algorithm is designed to find the shortest distance from one starting point (source) to every other point in a graph.

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree algorithms find a tree connecting all vertices with minimum total weight, cycle detection finds loops, and topological sort orders vertices. These are different tasks.

3. Final Answer:

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

4. Quick Check:

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

Hint: Dijkstra finds shortest paths from one start point [OK]

Common Mistakes:

• Confusing shortest path with minimum spanning tree
• Thinking it detects cycles
• Mixing it with topological sorting

2. Which of the following TypeScript code snippets correctly initializes the distance array for Dijkstra's Algorithm for a graph with 5 vertices?

easy

A. const dist: number[] = Array(5).fill(Infinity); dist[0] = 0;

B. const dist: number[] = new Array(5).map(() => 0);

C. const dist: number[] = Array(5).fill(0); dist[0] = Infinity;

D. const dist: number[] = Array(5).fill(null); dist[0] = 0;

Solution

1. Step 1: Understand initialization requirements

   Distances start as Infinity except the source vertex which is 0.

2. Step 2: Check each code snippet

   const dist: number[] = Array(5).fill(Infinity); dist[0] = 0; correctly fills with Infinity and sets source distance to 0. const dist: number[] = new Array(5).map(() => 0); fills with 0 incorrectly. const dist: number[] = Array(5).fill(0); dist[0] = Infinity; fills with 0 and sets source to Infinity, wrong. const dist: number[] = Array(5).fill(null); dist[0] = 0; fills with null, which is invalid for numeric distances.

3. Final Answer:

   const dist: number[] = Array(5).fill(Infinity); dist[0] = 0; -> Option A

4. Quick Check:

   Distance array init = Infinity except source 0 [OK]

Hint: Fill array with Infinity, set source distance to 0 [OK]

Common Mistakes:

• Using map on new Array without fill (returns undefined)
• Setting all distances to 0 initially
• Using null instead of numeric values

3. Given the following TypeScript code snippet implementing Dijkstra's Algorithm on a graph with edges: 0->1 (4), 0->2 (1), 2->1 (2), what is the final distance array after running from source vertex 0?

const graph = new Map>();
graph.set(0, [[1, 4], [2, 1]]);
graph.set(1, []);
graph.set(2, [[1, 2]]);

const dist = Array(3).fill(Infinity);
dist[0] = 0;
const visited = new Set<number>();

while (visited.size < 3) {
  let u = -1;
  let minDist = Infinity;
  for (let i = 0; i < 3; i++) {
    if (!visited.has(i) && dist[i] < minDist) {
      minDist = dist[i];
      u = i;
    }
  }
  if (u === -1) break;
  visited.add(u);
  for (const [v, w] of graph.get(u) || []) {
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}
console.log(dist);

medium

A. [0, 6, 1]

B. [0, 4, 1]

C. [Infinity, Infinity, Infinity]

D. [0, 3, 1]

Solution

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

   dist = [0, Infinity, Infinity], visited = {}.

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

   Pick 0: update dist[1] = 4, dist[2] = 1. visited = {0}. Pick 2 (dist=1): update dist[1] = min(4, 1+2=3) = 3. visited = {0,2}. Pick 1 (dist=3): no neighbors. visited = {0,1,2}.

3. Final Answer:

   [0, 3, 1] -> Option D

4. Quick Check:

   Distances after updates = [0, 3, 1] [OK]

Hint: Update neighbors only if new path is shorter [OK]

Common Mistakes:

• Not updating dist[1] from 4 to 3 via vertex 2
• Picking wrong vertex with smallest distance
• Ignoring visited set causing infinite loops

4. Identify the bug in the following TypeScript code snippet implementing Dijkstra's Algorithm:

const graph = new Map>();
graph.set(0, [[1, 7], [2, 9], [5, 14]]);
graph.set(1, [[2, 10], [3, 15]]);
graph.set(2, [[3, 11], [5, 2]]);
graph.set(3, [[4, 6]]);
graph.set(4, [[5, 9]]);
graph.set(5, []);
const dist: number[] = new Array(graph.size);
dist.fill(Infinity);
dist[0] = 0;
const visited = new Set<number>();

while (visited.size < graph.size) {
  let u = -1;
  let minDist = Infinity;
  for (let i = 0; i < graph.size; i++) {
    if (!visited.has(i) && dist[i] < minDist) {
      minDist = dist[i];
      u = i;
    }
  }
  visited.add(u);
  for (const [v, w] of graph.get(u) || []) {
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}

medium

A. dist array is not initialized before use

B. Adding vertex u to visited set before checking if u is -1

C. Using graph.size instead of graph.length in loop

D. Not updating dist[u] inside the loop

Solution

1. Step 1: Analyze the selection of vertex u

   If no unvisited vertex has finite dist, u remains -1.

2. Step 2: Check visited addition without validation

   Code adds u to visited without checking if u === -1, which can cause adding -1 and errors.

3. Final Answer:

   Adding vertex u to visited set before checking if u is -1 -> Option B

4. Quick Check:

   Check u !== -1 before visited.add(u) [OK]

Hint: Always verify selected vertex is valid before marking visited [OK]

Common Mistakes:

• Ignoring u === -1 case causing infinite loops
• Confusing graph.size with array length
• Not initializing dist array properly

5. You have a weighted graph with vertices 0 to 4 and edges: 0->1 (2), 0->2 (4), 1->2 (1), 1->3 (7), 2->4 (3), 3->4 (1). Using Dijkstra's Algorithm from source 0, what is the shortest path distance to vertex 4?

hard

A. 6

B. 7

C. 8

D. 9

Solution

1. Step 1: Calculate shortest distances step-by-step

   Start dist: [0,∞,∞,∞,∞] From 0: dist[1]=2, dist[2]=4 From 1: dist[2]=min(4,2+1=3)=3, dist[3]=2+7=9 From 2: dist[4]=3+3=6 From 3: dist[4]=min(6,9+1=10)=6

2. Step 2: Identify shortest distance to vertex 4

   Shortest distance to vertex 4 is 6 via path 0->1->2->4.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest path distance to 4 = 6 [OK]

Hint: Check all paths and pick minimum sum of edge weights [OK]

Common Mistakes:

• Ignoring shorter path via vertex 2
• Adding edges incorrectly
• Assuming direct edge is always shortest