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

Concept Flow - Dijkstra's Algorithm Single Source Shortest Path

Start: Initialize distances

↓

Set source distance = 0

↓

Add all nodes to unvisited set

↓

While unvisited nodes remain

↓

Pick node with smallest distance

↓

For each neighbor

↓

Calculate new distance

↓

If new distance < known distance

↓

Update distance and predecessor

↓

Mark current node visited

↓

Repeat until all visited

↓

Result: shortest distances from source

Dijkstra's algorithm starts with all nodes at infinite distance except the source. It repeatedly picks the closest unvisited node, updates neighbors' distances, and marks nodes visited until all shortest paths are found.

Execution Sample

DSA Go

graph := map[string]map[string]int{
  "A": {"B": 4, "C": 2},
  "B": {"C": 5, "D": 10},
  "C": {"E": 3},
  "D": {"F": 11},
  "E": {"D": 4},
  "F": {},
}
Dijkstra(graph, "A")

This code runs Dijkstra's algorithm on a graph starting from node A to find shortest paths.

Execution Table

Step	Operation	Current Node	Distances	Visited Nodes	Visual State
1	Initialize distances and unvisited	None	{"A":0, "B":∞, "C":∞, "D":∞, "E":∞, "F":∞}	[]	A(0), B(∞), C(∞), D(∞), E(∞), F(∞)
2	Pick node with smallest distance	A	{"A":0, "B":∞, "C":∞, "D":∞, "E":∞, "F":∞}	[]	A(0), B(∞), C(∞), D(∞), E(∞), F(∞)
3	Update neighbors of A	A	{"A":0, "B":4, "C":2, "D":∞, "E":∞, "F":∞}	[]	A(0) -> B(4), C(2), others ∞
4	Mark A visited	A	{"A":0, "B":4, "C":2, "D":∞, "E":∞, "F":∞}	[A]	Visited: A; Unvisited: B(4), C(2), D(∞), E(∞), F(∞)
5	Pick node with smallest distance	C	{"A":0, "B":4, "C":2, "D":∞, "E":∞, "F":∞}	[A]	Visited: A; Current: C(2)
6	Update neighbors of C	C	{"A":0, "B":4, "C":2, "D":∞, "E":5, "F":∞}	[A]	Updated E distance to 5 via C
7	Mark C visited	C	{"A":0, "B":4, "C":2, "D":∞, "E":5, "F":∞}	[A, C]	Visited: A, C; Unvisited: B(4), D(∞), E(5), F(∞)
8	Pick node with smallest distance	B	{"A":0, "B":4, "C":2, "D":∞, "E":5, "F":∞}	[A, C]	Current: B(4)
9	Update neighbors of B	B	{"A":0, "B":4, "C":2, "D":14, "E":5, "F":∞}	[A, C]	Updated D distance to 14 via B
10	Mark B visited	B	{"A":0, "B":4, "C":2, "D":14, "E":5, "F":∞}	[A, C, B]	Visited: A, C, B; Unvisited: D(14), E(5), F(∞)
11	Pick node with smallest distance	E	{"A":0, "B":4, "C":2, "D":14, "E":5, "F":∞}	[A, C, B]	Current: E(5)
12	Update neighbors of E	E	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":∞}	[A, C, B]	Updated D distance to 9 via E
13	Mark E visited	E	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":∞}	[A, C, B, E]	Visited: A, C, B, E; Unvisited: D(9), F(∞)
14	Pick node with smallest distance	D	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":∞}	[A, C, B, E]	Current: D(9)
15	Update neighbors of D	D	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":20}	[A, C, B, E]	Updated F distance to 20 via D
16	Mark D visited	D	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":20}	[A, C, B, E, D]	Visited: A, C, B, E, D; Unvisited: F(20)
17	Pick node with smallest distance	F	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":20}	[A, C, B, E, D]	Current: F(20)
18	Mark F visited	F	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":20}	[A, C, B, E, D, F]	All nodes visited, algorithm ends

💡 All nodes visited; shortest distances finalized

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	Final
Distances	{"A":0, "B":∞, "C":∞, "D":∞, "E":∞, "F":∞}	{"A":0, "B":4, "C":2, "D":∞, "E":∞, "F":∞}	{"A":0, "B":4, "C":2, "D":∞, "E":5, "F":∞}	{"A":0, "B":4, "C":2, "D":14, "E":5, "F":∞}	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":∞}	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":20}	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":20}	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":20}	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":20}	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":20}	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":20}	{"A":0, "B":4, "C":2, "D":9, "E":5, "F":20}
Visited Nodes	[]	[A]	[A, C]	[A, C, B]	[A, C, B, E]	[A, C, B, E, D]	[A, C, B, E, D, F]	[A, C, B, E, D, F]	[A, C, B, E, D, F]	[A, C, B, E, D, F]	[A, C, B, E, D, F]	[A, C, B, E, D, F]

Key Moments - 3 Insights

Why do we pick the node with the smallest current distance each time?

Because Dijkstra's algorithm guarantees that the shortest path to that node is finalized when it is picked. This is shown in execution_table rows 2, 5, 8, 11, 14, and 17 where the current node is chosen by smallest distance.

Why do distances get updated only if the new calculated distance is smaller?

Because we want the shortest path. If the new distance is larger or equal, it means we already have a better or equal path. This is visible in execution_table rows 3, 6, 9, and 12 where distances are updated only when smaller.

What happens when a node is marked visited?

It means we have found the shortest path to that node and won't revisit it. This is shown in execution_table rows 4, 7, 10, 13, 16, and 18 where nodes are added to the visited set.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the distance to node E?

A 2

B ∞

C 5

D 4

💡 Hint

Check the Distances column at step 6 in the execution_table.

At which step does node D's distance get updated to 9?

A Step 12

B Step 15

C Step 9

D Step 14

💡 Hint

Look for the update of D's distance in the Distances column in execution_table.

If the edge from E to D had weight 10 instead of 4, what would be the distance to D after step 12?

A 9

B 14

C ∞

D 5

💡 Hint

Consider how the update in step 12 depends on edge weight from E to D.

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 to every node from source.

Full Transcript

Dijkstra's algorithm starts by setting the distance to the source node as zero and all others as infinity. It keeps a set of unvisited nodes. At each step, it picks the unvisited node with the smallest known distance. Then it checks all neighbors of this node, calculates new distances through it, and updates if these are shorter. After processing neighbors, it marks the current node as visited, meaning its shortest distance is finalized. This repeats until all nodes are visited. The final distances represent the shortest paths from the source to every other node.

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 maximum flow in a network

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 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 C

4. Quick Check:

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

Hint: Remember: Dijkstra finds shortest paths from one source [OK]

Common Mistakes:

• Confusing Dijkstra with max flow algorithms
• Thinking it detects cycles
• Assuming it sorts vertices

2. Which Go data structure is most suitable to implement the priority queue needed in Dijkstra's Algorithm?

easy

A. container/heap package's IntHeap implementation

B. slice with manual sorting

C. map[string]int for distances

D. linked list for adjacency representation

Solution

1. Step 1: Identify priority queue requirement

   Dijkstra's Algorithm requires a priority queue to efficiently get the vertex with the smallest tentative distance.

2. Step 2: Choose Go's best priority queue

   Go's standard library provides the container/heap package which supports heap operations. Using IntHeap or a custom heap is the best choice for priority queue.

3. Final Answer:

   container/heap package's IntHeap implementation -> Option A

4. Quick Check:

   Priority queue in Go = container/heap [OK]

Hint: Use container/heap for priority queue in Go [OK]

Common Mistakes:

• Using slice without heap operations (slow)
• Using map for priority queue (wrong type)
• Using linked list for priority queue

3. What is the output of the following Go code snippet implementing Dijkstra's Algorithm for a graph with vertices 0,1,2 and edges: 0->1 (4), 0->2 (1), 2->1 (2)?

dist := []int{1e9, 1e9, 1e9}
dist[0] = 0
pq := &IntHeap{{0, 0}} // {distance, vertex}
heap.Init(pq)
for pq.Len() > 0 {
  cur := heap.Pop(pq).(Pair)
  d, u := cur.distance, cur.vertex
  if d > dist[u] { continue }
  for _, e := range graph[u] {
    v, w := e.vertex, e.weight
    if dist[u]+w < dist[v] {
      dist[v] = dist[u] + w
      heap.Push(pq, Pair{dist[v], v})
    }
  }
}
fmt.Println(dist)

medium

A. [0 4 1]

B. [0 3 1]

C. [0 6 1]

D. [1 3 1]

Solution

1. Step 1: Initialize distances and priority queue

   Distances start as [inf, inf, inf], then dist[0] = 0. Priority queue starts with vertex 0 at distance 0.

2. Step 2: Relax edges step-by-step

   From 0: dist[1] = min(inf, 0+4)=4, dist[2] = min(inf, 0+1)=1. Push (4,1) and (1,2). Next pop (1,2): from 2 to 1: dist[1] = min(4,1+2)=3. Update dist[1] to 3. Final distances: [0,3,1].

3. Final Answer:

   [0 3 1] -> Option B

4. Quick Check:

   Shortest distances = [0 3 1] [OK]

Hint: Relax edges and update distances carefully [OK]

Common Mistakes:

• Not updating dist[1] after checking edge 2->1
• Mixing up vertex indices
• Ignoring priority queue order

4. Identify the bug in this Go snippet of Dijkstra's Algorithm:

dist := make([]int, n)
for i := range dist {
  dist[i] = 1e9
}
dist[src] = 0
pq := &IntHeap{{0, src}}
heap.Init(pq)
for pq.Len() > 0 {
  cur := heap.Pop(pq).(Pair)
  d, u := cur.distance, cur.vertex
  if d < dist[u] { continue }
  for _, e := range graph[u] {
    v, w := e.vertex, e.weight
    if dist[u]+w < dist[v] {
      dist[v] = dist[u] + w
      heap.Push(pq, Pair{dist[v], v})
    }
  }
}

medium

A. The graph edges are not relaxed properly

B. dist array is not initialized with large values

C. Priority queue is not initialized before use

D. The condition should be 'if d > dist[u]' instead of 'if d < dist[u]'

Solution

1. Step 1: Check the distance comparison condition

   The condition 'if d < dist[u]' is incorrect because we want to skip processing if the current distance is greater than the stored distance.

2. Step 2: Correct condition for skipping outdated entries

   The correct condition is 'if d > dist[u]' to ignore stale entries in the priority queue.

3. Final Answer:

   The condition should be 'if d > dist[u]' instead of 'if d < dist[u]' -> Option D

4. Quick Check:

   Skip outdated if d > dist[u] [OK]

Hint: Skip if current distance is greater, not smaller [OK]

Common Mistakes:

• Using wrong comparison operator in distance check
• Not initializing dist with large values
• Forgetting to initialize priority queue

5. Given 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), Use Dijkstra's Algorithm to find the shortest path distance from vertex 0 to vertex 4. What is the shortest distance?

hard

A. 6

B. 7

C. 8

D. 5

Solution

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

   distances: [0, inf, inf, inf, inf]. From 0: dist[1]=2, dist[2]=4.

2. Step 2: Relax edges from vertex 1 and 2

   From 1: dist[2]=min(4,2+1)=3, dist[3]=2+7=9. From 2: dist[4]=3+3=6.

3. Step 3: Relax edges from vertex 3

   From 3: dist[4]=min(6,9+1=10)=6 (no change).

4. Final Answer:

   6 -> Option A

5. Quick Check:

   Shortest path 0->1->2->4 = 6 [OK]

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

Common Mistakes:

• Ignoring shorter path through vertex 2
• Adding edges incorrectly
• Not updating distances after relaxation