Dijkstra's Algorithm Single Source Shortest Path in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dijkstra's Algorithm on a Simple Graph

What is the shortest distance from node 0 to all other nodes after running Dijkstra's algorithm on this graph?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type Edge struct {
	dest, weight int
}

type Item struct {
	node, dist int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(Item))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func dijkstra(graph [][]Edge, start int) []int {
	dist := make([]int, len(graph))
	for i := range dist {
		dist[i] = 1 << 30
	}
	dist[start] = 0
	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, Item{start, 0})

	for pq.Len() > 0 {
		item := heap.Pop(pq).(Item)
		node, curDist := item.node, item.dist
		if curDist > dist[node] {
			continue
		}
		for _, e := range graph[node] {
			newDist := curDist + e.weight
			if newDist < dist[e.dest] {
				dist[e.dest] = newDist
				heap.Push(pq, Item{e.dest, newDist})
			}
		}
	}
	return dist
}

func main() {
	graph := [][]Edge{
		{{1, 4}, {2, 1}},
		{{3, 1}},
		{{1, 2}, {3, 5}},
		{},
	}
	dist := dijkstra(graph, 0)
	fmt.Println(dist)
}

A [0, 4, 1, 6]

B [0, 3, 1, 4]

C [0, 3, 1, 5]

D [0, 2, 1, 4]

💡 Hint

Trace the shortest paths from node 0 step by step, updating distances.

The shortest distances from node 0 are: to node 0 is 0, to node 2 is 1, to node 1 is 3 (via node 2), and to node 3 is 4 (via node 1).

🧠 Conceptual

intermediate

Understanding Dijkstra's Algorithm Behavior

Which statement correctly describes why Dijkstra's algorithm does not work with graphs containing negative edge weights?

A Because it updates distances only once per node, negative edges cause the algorithm to miss shorter paths found later.

B Because it uses a stack to store nodes, negative edges cause infinite loops.

C Because it uses breadth-first search, negative edges cause cycles that cannot be handled.

D Because it uses a priority queue that assumes distances only decrease, negative edges can cause incorrect shorter paths to be ignored.

💡 Hint

Think about how the algorithm finalizes distances and what negative edges imply.

Dijkstra's algorithm finalizes the shortest distance to a node once it is visited. Negative edges can create shorter paths after this finalization, which the algorithm cannot update.

🔧 Debug

advanced

Identify the Bug in Dijkstra's Implementation

What error will this Go code produce when running Dijkstra's algorithm on a graph with 3 nodes, if the graph is defined as graph := [][]Edge{{{1, 2}}, {{2, 3}}, {}} and start node is 0?

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type Edge struct {
	dest, weight int
}

type Item struct {
	node, dist int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(Item))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func dijkstra(graph [][]Edge, start int) []int {
	dist := make([]int, len(graph))
	for i := range dist {
		dist[i] = 1 << 30
	}
	dist[start] = 0
	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, Item{start, 0})

	for pq.Len() > 0 {
		item := heap.Pop(pq).(Item)
		node, curDist := item.node, item.dist
		if curDist > dist[node] {
			continue
		}
		for _, e := range graph[node] {
			newDist := curDist + e.weight
			if newDist < dist[e.dest] {
				dist[e.dest] = newDist
				heap.Push(pq, Item{e.dest, newDist})
			}
		}
	}
	return dist
}

func main() {
	graph := [][]Edge{{{1, 2}}, {{2, 3}}, {}}
	dist := dijkstra(graph, 0)
	fmt.Println(dist)
}

A No error; output is [0, 2, 5]

B Panic: interface conversion: interface {} is nil, not main.Item

C Panic: runtime error: index out of range

D No error; output is [0, 2, 3]

💡 Hint

Check the priority queue usage and the graph edges carefully.

The code correctly implements Dijkstra's algorithm and will output the shortest distances [0, 2, 5]. No runtime or panic errors occur.

❓ Predict Output

advanced

Output of Dijkstra's Algorithm with Multiple Paths

Given the graph below, what is the shortest distance array from node 0 after running Dijkstra's algorithm? Graph edges: 0 -> 1 (weight 1) 0 -> 2 (weight 4) 1 -> 2 (weight 2) 1 -> 3 (weight 6) 2 -> 3 (weight 3)

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

type Edge struct {
	dest, weight int
}

type Item struct {
	node, dist int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(Item))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func dijkstra(graph [][]Edge, start int) []int {
	dist := make([]int, len(graph))
	for i := range dist {
		dist[i] = 1 << 30
	}
	dist[start] = 0
	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, Item{start, 0})

	for pq.Len() > 0 {
		item := heap.Pop(pq).(Item)
		node, curDist := item.node, item.dist
		if curDist > dist[node] {
			continue
		}
		for _, e := range graph[node] {
			newDist := curDist + e.weight
			if newDist < dist[e.dest] {
				dist[e.dest] = newDist
				heap.Push(pq, Item{e.dest, newDist})
			}
		}
	}
	return dist
}

func main() {
	graph := [][]Edge{
		{{1, 1}, {2, 4}},
		{{2, 2}, {3, 6}},
		{{3, 3}},
		{},
	}
	dist := dijkstra(graph, 0)
	fmt.Println(dist)
}

A [0, 1, 4, 7]

B [0, 1, 2, 5]

C [0, 1, 3, 6]

D [0, 2, 3, 6]

💡 Hint

Consider the path 0->1->2->3 and compare distances carefully.

The shortest distances are 0 to 0 is 0, to 1 is 1, to 2 is 3 (via 1), and to 3 is 6 (via 2).

🧠 Conceptual

expert

Complexity Analysis of Dijkstra's Algorithm

What is the time complexity of Dijkstra's algorithm when implemented with a binary heap priority queue on a graph with V vertices and E edges?

A O(E log E)

B O(V^2)

C O(V log E)

D O((V + E) log V)

💡 Hint

Consider the operations on the priority queue and how many times they occur.

Each vertex is inserted and extracted from the priority queue once, and each edge may cause an update. Using a binary heap, each operation takes O(log V), so total is O((V + E) log V).

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