Dijkstra's Algorithm in Go: Implementation, Optimization, and Real-World Use

package graph

const Infinity = int(^uint(0) >> 1)

// Edge represents a directed weighted connection from one node to another.
type Edge struct {
    To     int
    Weight int
}

// Graph is an adjacency list indexed by node ID.
type Graph struct {
    Edges [][]Edge
    Size  int
}

func NewGraph(n int) *Graph {
    return &Graph{
        Edges: make([][]Edge, n),
        Size:  n,
    }
}

// AddEdge adds a directed edge. For undirected graphs, call twice.
func (g *Graph) AddEdge(from, to, weight int) {
    g.Edges[from] = append(g.Edges[from], Edge{To: to, Weight: weight})
}

package graph

// DijkstraNaive returns the shortest distance from start to every reachable node.
// Time complexity: O(V^2). Use DijkstraHeap for large sparse graphs.
func DijkstraNaive(g *Graph, start int) (dist []int, prev []int) {
    n := g.Size
    dist = make([]int, n)
    prev = make([]int, n)
    visited := make([]bool, n)

    for i := range dist {
        dist[i] = Infinity
        prev[i] = -1
    }
    dist[start] = 0

    for range n {
        // Find the unvisited node with the smallest tentative distance.
        u := -1
        for v := 0; v < n; v++ {
            if !visited[v] && (u == -1 || dist[v] < dist[u]) {
                u = v
            }
        }

        if u == -1 || dist[u] == Infinity {
            break // All remaining nodes are unreachable.
        }
        visited[u] = true

        for _, e := range g.Edges[u] {
            if alt := dist[u] + e.Weight; alt < dist[e.To] {
                dist[e.To] = alt
                prev[e.To] = u
            }
        }
    }

    return dist, prev
}

package graph

import "container/heap"

// heapItem is an entry in the priority queue.
type heapItem struct {
    node int
    dist int
}

type minHeap []heapItem

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

func (h *minHeap) Push(x any) {
    *h = append(*h, x.(heapItem))
}

func (h *minHeap) Pop() any {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[:n-1]
    return item
}

// DijkstraHeap returns shortest distances and the predecessor map from start.
// Time complexity: O((E + V) log V).
func DijkstraHeap(g *Graph, start int) (dist []int, prev []int) {
    n := g.Size
    dist = make([]int, n)
    prev = make([]int, n)

    for i := range dist {
        dist[i] = Infinity
        prev[i] = -1
    }
    dist[start] = 0

    pq := &minHeap{{node: start, dist: 0}}
    heap.Init(pq)

    for pq.Len() > 0 {
        item := heap.Pop(pq).(heapItem)
        u := item.node

        // Skip stale entries (a shorter path was already found).
        if item.dist > dist[u] {
            continue
        }

        for _, e := range g.Edges[u] {
            if alt := dist[u] + e.Weight; alt < dist[e.To] {
                dist[e.To] = alt
                prev[e.To] = u
                heap.Push(pq, heapItem{node: e.To, dist: alt})
            }
        }
    }

    return dist, prev
}

package graph

// ReconstructPath returns the node sequence on the shortest path from start to end.
// Returns nil if end is unreachable from start.
func ReconstructPath(prev []int, start, end int) []int {
    if prev[end] == -1 && end != start {
        return nil // end is unreachable
    }

    var path []int
    for at := end; at != -1; at = prev[at] {
        path = append(path, at)
    }

    // Reverse in place.
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
        path[i], path[j] = path[j], path[i]
    }
    return path
}

package main

import (
    "fmt"
    "graph"
)

func main() {
    g := graph.NewGraph(6) // nodes 0-5

    g.AddEdge(0, 1, 7)
    g.AddEdge(0, 2, 9)
    g.AddEdge(0, 5, 14)
    g.AddEdge(1, 2, 10)
    g.AddEdge(1, 3, 15)
    g.AddEdge(2, 3, 11)
    g.AddEdge(2, 5, 2)
    g.AddEdge(3, 4, 6)
    g.AddEdge(4, 5, 9)

    dist, prev := graph.DijkstraHeap(g, 0)

    fmt.Println("Distance from 0 to 4:", dist[4]) // 26
    path := graph.ReconstructPath(prev, 0, 4)
    fmt.Println("Path:", path) // [0 2 5 4] -- but wait, 5->4 is not in our edges
    // Correct path for this graph: 0->2->3->4, cost = 9+11+6 = 26
}

package deps

import "graph"

// ServiceGraph models service-to-service dependencies with latency weights.
type ServiceGraph struct {
    g         *graph.Graph
    nameToID  map[string]int
    idToName  []string
}

func NewServiceGraph(services []string) *ServiceGraph {
    n := len(services)
    sg := &ServiceGraph{
        g:        graph.NewGraph(n),
        nameToID: make(map[string]int, n),
        idToName: make([]string, n),
    }
    for i, name := range services {
        sg.nameToID[name] = i
        sg.idToName[i] = name
    }
    return sg
}

func (sg *ServiceGraph) AddDependency(from, to string, latencyMs int) {
    sg.g.AddEdge(sg.nameToID[from], sg.nameToID[to], latencyMs)
}

// CriticalPath returns the highest-latency path from entry to target service.
func (sg *ServiceGraph) CriticalPath(from, to string) ([]string, int) {
    start := sg.nameToID[from]
    end := sg.nameToID[to]
    dist, prev := graph.DijkstraHeap(sg.g, start)

    nodeIDs := graph.ReconstructPath(prev, start, end)
    names := make([]string, len(nodeIDs))
    for i, id := range nodeIDs {
        names[i] = sg.idToName[id]
    }
    return names, dist[end]
}