Dijkstra's Algorithm Single Source Shortest Path in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance slice with maximum integer values.

DSA Go

dist := make([]int, n)
for i := 0; i < n; i++ {
    dist[i] = [1]
}

Drag options to blanks, or click blank then click option'

Amath.MaxInt32

B0

C-1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing distances to 0 which means all nodes are at zero distance initially.

Using negative values which are invalid for distances.

We initialize distances to the maximum integer value to represent infinity before starting Dijkstra's algorithm.

2fill in blank

medium

Complete the code to update the distance if a shorter path is found.

DSA Go

if dist[u]+weight < dist[v] {
    dist[v] = [1]
}

Drag options to blanks, or click blank then click option'

Aweight

Bdist[u] + weight

Cdist[u]

Ddist[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning dist[u] instead of dist[u] + weight.

Assigning weight alone which ignores the distance to u.

We update dist[v] to the new shorter distance which is dist[u] plus the edge weight.

3fill in blank

hard

Fix the error in the priority queue pop operation to get the node with the smallest distance.

DSA Go

current := pq.[1]()

Drag options to blanks, or click blank then click option'

APop

BPush

CPeek

DRemove

Attempts:

3 left

💡 Hint

Common Mistakes

Using Push which adds an element instead of removing.

Using Peek which only views the element without removing.

Pop removes and returns the element with the smallest priority (distance) from the priority queue.

4fill in blank

hard

Fill both blanks to correctly iterate over neighbors and update distances.

DSA Go

for _, [1] := range graph[u] {
    v, weight := [2].node, [2].weight
    if dist[u]+weight < dist[v] {
        dist[v] = dist[u] + weight
        pq.Push(Item{node: v, priority: dist[v]})
    }
}

Drag options to blanks, or click blank then click option'

Aedge

Bneighbor

Cnode

Dvertex

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names inconsistently.

Using variable names that do not match the graph's edge struct.

We use 'edge' as the variable name for each neighbor in graph[u] and access its node and weight fields.

5fill in blank

hard

Fill all three blanks to correctly initialize the priority queue and set the source distance.

DSA Go

dist := make([]int, n)
for i := 0; i < n; i++ {
    dist[i] = [1]
}
dist[[2]] = 0
pq := &PriorityQueue{}
pq.[3](Item{node: [2], priority: 0})

Drag options to blanks, or click blank then click option'

Amath.MaxInt32

Bsource

CPush

DPop

Attempts:

3 left

💡 Hint

Common Mistakes

Not setting source distance to zero.

Using Pop instead of Push to add to the priority queue.

Distances are initialized to max int, source distance set to 0, and source node pushed into the priority queue.

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