Dijkstra and stale heap entries

type Edge struct{ To, Weight int }
type candidate struct{ Node, Cost int }
type candidates []candidate

func (h candidates) Len() int           { return len(h) }
func (h candidates) Less(i, j int) bool { return h[i].Cost < h[j].Cost }
func (h candidates) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *candidates) Push(x any)        { *h = append(*h, x.(candidate)) }
func (h *candidates) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

// Requires container/heap. Caller validates node IDs, nonnegative
// weights and that every path cost fits int. -1 means unreachable.
func ShortestDistances(adj [][]Edge, start int) []int {
	d := make([]int, len(adj))
	for i := range d {
		d[i] = -1
	}
	d[start] = 0
	h := &candidates{{Node: start, Cost: 0}}
	for h.Len() > 0 {
		current := heap.Pop(h).(candidate)
		if current.Cost != d[current.Node] {
			continue
		}
		for _, e := range adj[current.Node] {
			cost := current.Cost + e.Weight
			if d[e.To] < 0 || cost < d[e.To] {
				d[e.To] = cost
				heap.Push(h, candidate{Node: e.To, Cost: cost})
			}
		}
	}
	return d
}