Dijkstra's Algorithm Single Source Shortest Path in DSA Go

Mental Model

Find the shortest path from one starting point to all other points by always choosing the closest unvisited point next.

Analogy: Imagine you are in a city and want to find the shortest way to every other city by always traveling first to the nearest city you haven't visited yet.

Start: A
Graph:
A --2--> B
A --5--> C
B --1--> C
C --2--> D
D --1--> E

Distances:
A: 0
B: ∞
C: ∞
D: ∞
E: ∞

Visited: none

Dry Run Walkthrough

Input: Graph with edges: A-B(2), A-C(5), B-C(1), C-D(2), D-E(1); start at A

Goal: Find shortest distances from A to all nodes

Step 1: Initialize distances: A=0, others=∞; start with A as current node

Distances: A[0], B[∞], C[∞], D[∞], E[∞]
Visited: {}
Current: A

Why: We start from A with distance zero and others unknown

Step 2: Update neighbors of A: B=2, C=5; mark A visited

Distances: A[0], B[2], C[5], D[∞], E[∞]
Visited: {A}
Current: B (closest unvisited)

Why: From A, we can reach B and C with given weights

Step 3: Update neighbors of B: C=min(5, 2+1=3)=3; mark B visited

Distances: A[0], B[2], C[3], D[∞], E[∞]
Visited: {A,B}
Current: C (closest unvisited)

Why: B offers a shorter path to C than direct from A

Step 4: Update neighbors of C: D=3+2=5; mark C visited

Distances: A[0], B[2], C[3], D[5], E[∞]
Visited: {A,B,C}
Current: D (closest unvisited)

Why: From C, we can reach D with total distance 5

Step 5: Update neighbors of D: E=5+1=6; mark D visited

Distances: A[0], B[2], C[3], D[5], E[6]
Visited: {A,B,C,D}
Current: E (closest unvisited)

Why: From D, we can reach E with total distance 6

Step 6: Mark E visited; no neighbors to update

Distances: A[0], B[2], C[3], D[5], E[6]
Visited: {A,B,C,D,E}
Current: none

Why: All nodes visited, algorithm ends

Result:

Final distances:
A -> 0
B -> 2
C -> 3
D -> 5
E -> 6

Annotated Code

DSA Go

package main

import (
	"container/heap"
	"fmt"
	"math"
)

type Edge struct {
	dest   string
	weight int
}

type Graph map[string][]Edge

type Item struct {
	node     string
	distance int
	index    int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].distance < pq[j].distance
}
func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	old[n-1] = nil
	item.index = -1
	*pq = old[0 : n-1]
	return item
}

func Dijkstra(graph Graph, start string) map[string]int {
	dist := make(map[string]int)
	for node := range graph {
		dist[node] = math.MaxInt64
	}
	dist[start] = 0

	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, &Item{node: start, distance: 0})

	visited := make(map[string]bool)

	for pq.Len() > 0 {
		item := heap.Pop(pq).(*Item)
		current := item.node

		if visited[current] {
			continue
		}
		visited[current] = true

		for _, edge := range graph[current] {
			if visited[edge.dest] {
				continue
			}
			newDist := dist[current] + edge.weight
			if newDist < dist[edge.dest] {
				dist[edge.dest] = newDist
				heap.Push(pq, &Item{node: edge.dest, distance: newDist})
			}
		}
	}

	return dist
}

func main() {
	graph := Graph{
		"A": {{"B", 2}, {"C", 5}},
		"B": {{"C", 1}},
		"C": {{"D", 2}},
		"D": {{"E", 1}},
		"E": {},
	}

	distances := Dijkstra(graph, "A")

	for node, dist := range distances {
		fmt.Printf("%s -> %d\n", node, dist)
	}
}

dist := make(map[string]int) for node := range graph { dist[node] = math.MaxInt64 } dist[start] = 0

Initialize distances to infinity except start node zero

pq := &PriorityQueue{} heap.Init(pq) heap.Push(pq, &Item{node: start, distance: 0})

Initialize priority queue with start node distance zero

for pq.Len() > 0 { item := heap.Pop(pq).(*Item) current := item.node if visited[current] { continue } visited[current] = true

Extract closest unvisited node and mark visited

for _, edge := range graph[current] { if visited[edge.dest] { continue } newDist := dist[current] + edge.weight if newDist < dist[edge.dest] { dist[edge.dest] = newDist heap.Push(pq, &Item{node: edge.dest, distance: newDist}) } }

Update distances for neighbors if shorter path found and add to queue

Output

A -> 0

B -> 2

C -> 3

D -> 5

E -> 6

Complexity Analysis

Time: O(E log V) because each edge is processed and priority queue operations take log V time

Space: O(V + E) because we store graph edges and distance map for all vertices

vs Alternative: Compared to Bellman-Ford (O(VE)), Dijkstra is faster on graphs with non-negative weights using a priority queue

Edge Cases

Graph with isolated nodes (no edges)

Distances remain infinity except start node zero

DSA Go

dist := make(map[string]int)
for node := range graph {
	dist[node] = math.MaxInt64
}

Graph with zero-weight edges

Algorithm correctly updates distances to zero where applicable

DSA Go

newDist := dist[current] + edge.weight
if newDist < dist[edge.dest] {

Start node not in graph

Distances map will be empty or no updates; algorithm returns empty or zero map

DSA Go

dist[start] = 0

When to Use This Pattern

When you need shortest paths from one point to many others in a graph with non-negative weights, use Dijkstra's algorithm because it efficiently finds minimum distances using a priority queue.

Common Mistakes

Mistake: Not marking nodes as visited and revisiting them multiple times
Fix: Use a visited map to skip already processed nodes to avoid infinite loops and redundant work

Mistake: Updating distances without checking if new distance is smaller
Fix: Only update and push to queue if new calculated distance is less than current stored distance

Mistake: Using a simple queue instead of a priority queue
Fix: Use a priority queue to always pick the closest unvisited node next for correct shortest path calculation

Summary

Finds shortest distances from one start node to all others in a weighted graph with non-negative edges.

Use when you need efficient shortest path calculations from a single source in graphs without negative weights.

Always pick the closest unvisited node next and update neighbors to ensure shortest paths.

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