How do I implement Dijkstra's algorithm in Go?

Dijkstra's algorithm is a popular graph search algorithm used to find the shortest path between nodes in a weighted graph. Here is a simple implementation of Dijkstra's algorithm in Go.


package main

import (
    "container/heap"
    "fmt"
)

// Item represents a node in the graph
type Item struct {
    value    string // The value of the item
    priority int    // The priority (distance from source)
    index    int    // The index of the item in the heap
}

// PriorityQueue implements heap.Interface and holds Items
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

// Push and Pop methods for the priority queue
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]
    *pq = old[0 : n-1]
    return item
}

// Dijkstra's function to find the shortest path from a source node
func Dijkstra(graph map[string]map[string]int, start string) map[string]int {
    distances := make(map[string]int)
    for k := range graph {
        distances[k] = int(^uint(0) >> 1) // Set to infinity
    }
    distances[start] = 0

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

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

        for neighbor, weight := range graph[current.value] {
            distance := distances[current.value] + weight
            if distance < distances[neighbor] {
                distances[neighbor] = distance
                heap.Push(pq, &Item{
                    value:    neighbor,
                    priority: distance,
                })
            }
        }
    }

    return distances
}

func main() {
    graph := map[string]map[string]int{
        "A": {"B": 1, "C": 4},
        "B": {"A": 1, "C": 2, "D": 5},
        "C": {"A": 4, "B": 2, "D": 1},
        "D": {"B": 5, "C": 1},
    }
    
    distances := Dijkstra(graph, "A")
    fmt.Println("Shortest distances from A:", distances)
}

How do I implement Dijkstra's algorithm in Go?

Popular Topics

Recent Languages

How do I implement Dijkstra's algorithm in Go?

Related Questions

Popular Topics

Recent Languages