Кратчайшие пути: алгоритм Дейкстры

import (
    "container/heap"
    "math"
)

type Item struct{ vertex, dist int }
type PQ []Item

func (pq PQ) Len() int            { return len(pq) }
func (pq PQ) Less(i, j int) bool  { return pq[i].dist < pq[j].dist }
func (pq PQ) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x any)         { *pq = append(*pq, x.(Item)) }
func (pq *PQ) Pop() any           { old := *pq; n := len(old); v := old[n-1]; *pq = old[:n-1]; return v }

func dijkstra(g *ListGraph, src int) []int {
    dist := make([]int, g.n)
    for i := range dist { dist[i] = math.MaxInt }
    dist[src] = 0

    pq := &PQ{{src, 0}}
    heap.Init(pq)

    for pq.Len() > 0 {
        item := heap.Pop(pq).(Item)
        v, d := item.vertex, item.dist
        if d > dist[v] { continue } // устаревший элемент
        for _, e := range g.Neighbors(v) {
            if nd := dist[v] + e.Weight; nd < dist[e.To] {
                dist[e.To] = nd
                heap.Push(pq, Item{e.To, nd})
            }
        }
    }
    return dist
}

func dijkstraWithPath(g *ListGraph, src int) ([]int, []int) {
    dist := make([]int, g.n)
    prev := make([]int, g.n)
    for i := range dist { dist[i] = math.MaxInt; prev[i] = -1 }
    dist[src] = 0
    // ... (как выше, но добавляем: prev[e.To] = v)

    return dist, prev
}

func reconstructPath(prev []int, dst int) []int {
    var path []int
    for dst != -1 { path = append([]int{dst}, path...); dst = prev[dst] }
    return path
}