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

Concept Flow - Dijkstra's Algorithm Single Source Shortest Path

Start with source node

↓

Initialize distances: source=0, others=∞

↓

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 and enqueue neighbor

↓

Repeat until all nodes processed

↓

Result: shortest distances from source

Dijkstra's algorithm finds shortest paths from one node to all others by repeatedly picking the closest unvisited node and updating neighbors.

Execution Sample

DSA Javascript

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 in a weighted graph using Dijkstra's algorithm.

Execution Table

Step	Operation	Current Node	Distances	Priority Queue	Visual State
1	Initialize distances	A	{"A":0,"B":∞,"C":∞,"D":∞}	[A(0)]	A(0) -> B(∞) -> C(∞) -> D(∞)
2	Extract min node	A	{"A":0,"B":∞,"C":∞,"D":∞}	[]	Visited A(0)
3	Update neighbors of A	A	{"A":0,"B":1,"C":4,"D":∞}	[B(1), C(4)]	A(0) -> B(1) -> C(4) -> D(∞)
4	Extract min node	B	{"A":0,"B":1,"C":4,"D":∞}	[C(4)]	Visited B(1)
5	Update neighbors of B	B	{"A":0,"B":1,"C":3,"D":6}	[C(3), D(6)]	A(0) -> B(1) -> C(3) -> D(6)
6	Extract min node	C	{"A":0,"B":1,"C":3,"D":6}	[D(6)]	Visited C(3)
7	Update neighbors of C	C	{"A":0,"B":1,"C":3,"D":4}	[D(4)]	A(0) -> B(1) -> C(3) -> D(4)
8	Extract min node	D	{"A":0,"B":1,"C":3,"D":4}	[]	Visited D(4)
9	No neighbors to update	D	{"A":0,"B":1,"C":3,"D":4}	[]	All nodes visited
10	End	-	{"A":0,"B":1,"C":3,"D":4}	[]	Final shortest distances

💡 Priority queue empty, all nodes processed

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
Distances	{"A":0,"B":∞,"C":∞,"D":∞}	{"A":0,"B":∞,"C":∞,"D":∞}	{"A":0,"B":1,"C":4,"D":∞}	{"A":0,"B":1,"C":4,"D":∞}	{"A":0,"B":1,"C":3,"D":6}	{"A":0,"B":1,"C":3,"D":6}	{"A":0,"B":1,"C":3,"D":4}	{"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(4)]	[C(3), D(6)]	[D(6)]	[D(4)]	[]	[]

Key Moments - 3 Insights

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

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

Why do we use a priority queue to pick the next node?

The priority queue helps pick the node with the smallest current distance efficiently. This ensures we always explore the closest unvisited node next. See execution_table steps 2, 4, 6, and 8 where the min node is extracted.

What happens if a node has no neighbors?

If a node has no neighbors, no distances are updated and the algorithm moves on. See step 9 where node D has no neighbors, so no updates occur.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the updated distance for node C?

A 4

B 6

C 3

D 1

💡 Hint

Check the Distances column at step 5 in execution_table

At which step does the priority queue become empty for the first time?

A Step 2

B Step 4

C Step 8

D Step 10

💡 Hint

Look at the Priority Queue column in execution_table rows

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

A 6

B 3

C 4

D 7

💡 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 source node
- Uses distances map, initialized with 0 for source, ∞ for others
- Uses priority queue to pick closest unvisited node
- Updates neighbors if shorter path found
- Stops when all nodes visited
- Result: shortest distances from source to all nodes

Full Transcript

Dijkstra's algorithm starts with the source node, setting its distance to zero and all others to infinity. It uses a priority queue to pick the node with the smallest known distance. For each picked node, it updates the distances of its neighbors if a shorter path is found through it. This process repeats until all nodes are visited and the priority queue is empty. The final distances map shows the shortest path lengths from the source to every node in the graph.

Practice

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

easy

A. To sort vertices in topological order

B. To find the maximum flow in a network

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 algorithm's goal

   Dijkstra's Algorithm is designed to find the shortest paths from one starting point (source) to all other points in a graph with non-negative edge weights.

2. Step 2: Compare with other graph algorithms

   Other algorithms like max flow or cycle detection serve different purposes, so they do not match Dijkstra's goal.

3. Final Answer:

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

4. Quick Check:

   Shortest path from one source = To find the shortest path from a single source to all other vertices [OK]

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

Common Mistakes:

• Confusing Dijkstra with max flow 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 JavaScript?

easy

A. const dist = new Array(n).fill(Infinity); dist[source] = 0;

B. const dist = Array(n).fill(0); dist[source] = Infinity;

C. const dist = new Array(n).fill(null); dist[source] = 0;

D. const dist = new Array(n).fill(-1); dist[source] = 0;

Solution

1. Step 1: Understand distance initialization

   Distances to all nodes except the source should start as Infinity to represent unknown paths, and the source distance is 0.

2. Step 2: Check each option

   const dist = new Array(n).fill(Infinity); dist[source] = 0; correctly sets all distances to Infinity and source to 0. Others either set wrong initial values or invert source distance.

3. Final Answer:

   const dist = new Array(n).fill(Infinity); dist[source] = 0; -> Option A

4. Quick Check:

   Distance array starts with Infinity except source = const dist = new Array(n).fill(Infinity); dist[source] = 0; [OK]

Hint: Start distances as Infinity, source as 0 [OK]

Common Mistakes:

• Setting source distance to Infinity
• Using 0 for all distances initially
• Using null or -1 incorrectly

3. Consider the following JavaScript code snippet implementing part of Dijkstra's Algorithm. What will be the output of the distance array after running this code?

const graph = {
  0: [{node:1, weight:4}, {node:2, weight:1}],
  1: [{node:3, weight:1}],
  2: [{node:1, weight:2}, {node:3, weight:5}],
  3: []
};
const dist = [0, Infinity, Infinity, Infinity];
const visited = new Set();

function dijkstra() {
  while (visited.size < 4) {
    let u = -1;
    let minDist = Infinity;
    for (let i = 0; i < 4; i++) {
      if (!visited.has(i) && dist[i] < minDist) {
        minDist = dist[i];
        u = i;
      }
    }
    visited.add(u);
    for (const neighbor of graph[u]) {
      if (dist[u] + neighbor.weight < dist[neighbor.node]) {
        dist[neighbor.node] = dist[u] + neighbor.weight;
      }
    }
  }
}
dijkstra();
console.log(dist);

medium

A. [0, 4, 1, 6]

B. [0, 3, 1, 4]

C. [0, 2, 1, 3]

D. [0, 5, 1, 7]

Solution

1. Step 1: Trace initial distances and first iteration

   Start dist = [0, Infinity, Infinity, Infinity]. Pick node 0 (dist=0). Update neighbors: node 1 = 4, node 2 = 1.

2. Step 2: Next iterations and updates

   Pick node 2 (dist=1). Update node 1: min(4, 1+2=3) = 3; node 3: min(Infinity, 1+5=6) = 6. Pick node 1 (dist=3). Update node 3: min(6, 3+1=4) = 4. Pick node 3 (dist=4). No neighbors.

3. Final Answer:

   [0, 3, 1, 4] -> Option B

4. Quick Check:

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

Hint: Pick unvisited node with smallest dist, update neighbors [OK]

Common Mistakes:

• Not updating distances correctly
• Choosing wrong next node
• Ignoring neighbor updates

4. The following code snippet is intended to implement Dijkstra's Algorithm but contains a bug. What is the bug?

const dist = new Array(n).fill(Infinity);
dist[source] = 0;
const visited = new Set();

while (visited.size < n) {
  let u = -1;
  let minDist = Infinity;
  for (let i = 0; i < n; i++) {
    if (dist[i] < minDist) {
      minDist = dist[i];
      u = i;
    }
  }
  visited.add(u);
  for (const neighbor of graph[u]) {
    if (dist[u] + neighbor.weight < dist[neighbor.node]) {
      dist[neighbor.node] = dist[u] + neighbor.weight;
    }
  }
}

medium

A. The visited set is not updated inside the loop

B. The distance array is not initialized correctly

C. The code does not check if node i is already visited before selecting u

D. The neighbor weights are not added to dist[u]

Solution

1. Step 1: Analyze node selection loop

   The loop selects node u with smallest dist[i] but does not check if i is already visited, so it may pick visited nodes again.

2. Step 2: Understand impact of missing visited check

   Without skipping visited nodes, the algorithm can loop incorrectly or update distances wrongly, breaking correctness.

3. Final Answer:

   The code does not check if node i is already visited before selecting u -> Option C

4. Quick Check:

   Must skip visited nodes when picking u = The code does not check if node i is already visited before selecting u [OK]

Hint: Always skip visited nodes when choosing next node [OK]

Common Mistakes:

• Forgetting to check visited nodes in selection
• Incorrect distance initialization
• Not updating visited set

5. You have a weighted graph with 5 nodes (0 to 4). The edges are:

• 0 -> 1 (2)
• 0 -> 2 (4)
• 1 -> 2 (1)
• 1 -> 3 (7)
• 2 -> 4 (3)
• 3 -> 4 (1)

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

hard

A. 6

B. 7

C. 8

D. 5

Solution

1. Step 1: Trace shortest paths from node 0

   Start dist: 0=0, others=Infinity. From 0: dist[1]=2, dist[2]=4.

2. Step 2: Update distances via neighbors

   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.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest distance to node 4 = 6 [OK]

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

Common Mistakes:

• Ignoring shorter path through node 2
• Adding wrong edge weights
• Not updating distances properly