Dijkstra's Algorithm Single Source Shortest Path in DSA Go - Build from Scratch

Dijkstra's Algorithm Single Source Shortest Path

📖 Scenario: You are working as a city planner. You have a map of intersections connected by roads with distances. You want to find the shortest distance from a starting intersection to all other intersections.

🎯 Goal: Build a program that uses Dijkstra's algorithm to find the shortest paths from a given start intersection to all others in the city map.

📋 What You'll Learn

Create a graph using a map of maps to represent intersections and road distances

Use a variable to hold the starting intersection

Implement Dijkstra's algorithm to find shortest distances

Print the shortest distances from the start intersection to all others

💡 Why This Matters

🌍 Real World

City planners and GPS apps use shortest path algorithms like Dijkstra's to find quickest routes between locations.

💼 Career

Understanding Dijkstra's algorithm is important for software engineers working on navigation, mapping, and network routing systems.

1

Create the city map graph

Create a variable called graph as a map[string]map[string]int with these exact entries: "A": {"B": 4, "C": 2}, "B": {"A": 4, "C": 5, "D": 10}, "C": {"A": 2, "B": 5, "D": 3}, "D": {"B": 10, "C": 3}.

DSA Go

var graph = map[string]map[string]int{
    // Your code here
}

Hint

Use a map where keys are intersection names and values are maps of connected intersections with distances.

2

Set the starting intersection

Create a variable called start and set it to the string "A".

DSA Go

package main

import "fmt"

func main() {
    var graph = map[string]map[string]int{
        "A": {"B": 4, "C": 2},
        "B": {"A": 4, "C": 5, "D": 10},
        "C": {"A": 2, "B": 5, "D": 3},
        "D": {"B": 10, "C": 3},
    }
    // Your code here
}

Hint

Use a string variable named start and assign it the value "A".

3

Implement Dijkstra's algorithm

Implement Dijkstra's algorithm inside main() to find shortest distances from start. Create a map called distances to hold shortest distances with initial values set to a large number (e.g., 1<<31 - 1). Set distances[start] to 0. Use a map called visited to track visited intersections. Use a loop to pick the unvisited intersection with the smallest distance, update distances for its neighbors, and mark it visited until all are visited.

DSA Go

package main

import "fmt"

func main() {
    var graph = map[string]map[string]int{
        "A": {"B": 4, "C": 2},
        "B": {"A": 4, "C": 5, "D": 10},
        "C": {"A": 2, "B": 5, "D": 3},
        "D": {"B": 10, "C": 3},
    }
    start := "A"
    // Your code here
}

Hint

Use maps to track distances and visited nodes. Pick the closest unvisited node each time and update neighbors' distances.

4

Print the shortest distances

Use a for loop to print each intersection and its shortest distance from start in the format "A: 0", "B: 4", etc.

DSA Go

package main

import "fmt"

func main() {
    var graph = map[string]map[string]int{
        "A": {"B": 4, "C": 2},
        "B": {"A": 4, "C": 5, "D": 10},
        "C": {"A": 2, "B": 5, "D": 3},
        "D": {"B": 10, "C": 3},
    }
    start := "A"

    distances := make(map[string]int)
    visited := make(map[string]bool)

    maxInt := int(^uint(0) >> 1)

    for node := range graph {
        distances[node] = maxInt
    }
    distances[start] = 0

    for {
        minDistance := maxInt
        var currentNode string
        for node, dist := range distances {
            if !visited[node] && dist < minDistance {
                minDistance = dist
                currentNode = node
            }
        }

        if minDistance == maxInt {
            break
        }

        visited[currentNode] = true

        for neighbor, weight := range graph[currentNode] {
            if !visited[neighbor] {
                newDist := distances[currentNode] + weight
                if newDist < distances[neighbor] {
                    distances[neighbor] = newDist
                }
            }
        }
    }

    // Print shortest distances
    // Your code here
}

Hint

Use fmt.Printf("%s: %d\n", node, dist) inside a for loop over distances.

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