L'Algoritmo di Dijkstra in Go: Implementazione, Ottimizzazione e Uso Reale

package graph

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

// Edge rappresenta una connessione diretta e pesata da un nodo a un altro.
type Edge struct {
    To     int
    Weight int
}

// Graph e una lista di adiacenza indicizzata per ID nodo.
type Graph struct {
    Edges [][]Edge
    Size  int
}

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

// AddEdge aggiunge un arco diretto. Per grafi non diretti, chiama due volte.
func (g *Graph) AddEdge(from, to, weight int) {
    g.Edges[from] = append(g.Edges[from], Edge{To: to, Weight: weight})
}

package graph

// DijkstraNaive restituisce la distanza minima da start a ogni nodo raggiungibile.
// Complessita temporale: O(V^2). Usa DijkstraHeap per grafi sparsi di grandi dimensioni.
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 {
        // Trova il nodo non visitato con la distanza tentativa minima.
        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 // Tutti i nodi rimanenti non sono raggiungibili.
        }
        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"

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 restituisce le distanze minime e la mappa dei predecessori da start.
// Complessita temporale: 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

        // Salta le voci obsolete (e gia stato trovato un percorso piu breve).
        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 restituisce la sequenza di nodi sul percorso minimo da start a end.
// Restituisce nil se end non e raggiungibile da start.
func ReconstructPath(prev []int, start, end int) []int {
    if prev[end] == -1 && end != start {
        return nil // end non e raggiungibile
    }

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

    // Inversione 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 deps

import "graph"

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 restituisce il percorso a latenza minima dal servizio from al servizio to.
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]
}