直接用 container/heap 实现 Dijkstra 易出错，因标准库无 decrease-key 支持，需靠“懒删除”：重复入堆 + 出队时检查 dist[cur.to] < cur.dist，否则跳过；初始化距离为 math.MaxInt64，松弛成功即入堆新节点。
为什么直接用 container/heap 实现 Dijkstra 容易出错
因为 Go 标准库没有内置的优先队列更新操作，而 Dijkstra 算法在松弛边时经常需要「降低某个已入队节点的权重」——但 heap.Fix 要求你提前知道该节点在堆中的索引，而标准 *Heap 类型不暴露索引映射。结果就是：要么重复入堆（靠后续跳过旧条目兜底），要么自己维护索引表，否则会漏更新或算错距离。
常见错误现象：distance[v] == math.MaxInt64 却仍被当作未访问节点处理；或同一节点多次 pop 出来，却没检查是否已被更优路径处理过。
- 必须在 pop 后立刻判断
dist[current] < currentDist，若成立则 直接 continue - 每次 relax 成功后，把新
{to, newDist}推进堆，不要尝试修改已有节点 - 初始化距离数组时，用
math.MaxInt64而非-1，避免和 0 权重边混淆
如何写一个能跑通的最小可用 Dijkstra 版本
核心是「懒删除」+ 堆存元组。不需要支持 decrease-key，靠重复入堆 + 入队前不校验、出队后校验来保正确性。适用于大多数图规模（1e4 节点以内）。
// Node 表示堆中元素：目标节点 ID 和当前已知最短距离
type Node struct {
to int
dist int64
}
func (n Node) Less(other interface{}) bool {
return n.dist < other.(Node).dist
}
// ... 实现 Push/Pop 满足 heap.Interface
func dijkstra(graph [][][2]int, start int) []int64 {
n := len(graph)
dist := make([]int64, n)
for i := range dist {
dist[i] = math.MaxInt64
}
dist[start] = 0
h := &Heap{}
heap.Init(h)
heap.Push(h, Node{to: start, dist: 0})
for h.Len() > 0 {
cur := heap.Pop(h).(Node)
if cur.dist > dist[cur.to] {
continue // 已有更短路径，跳过
}
for _, edge := range graph[cur.to] {
to, weight := edge[0], int64(edge[1])
newDist := cur.dist + weight
if newDist < dist[to] {
dist[to] = newDist
heap.Push(h, Node{to: to, dist: newDist})
}
}
}
return dist
}
邻接表用 [][][2]int 还是 map[int][][2]int
取决于图是否稀疏、节点 ID 是否连续。如果节点编号是 0..n-1 且 n 已知，用切片更快更省内存；如果节点 ID 是随机大整数（如 UUID 哈希后取模）、或动态增删频繁，用 map 更安全，但要注意 key 查找开销和 GC 压力。
Alibabacloud Sdk Client Initialization For Golang
下载
初始化并管理阿里云SDK Go 客户端，涵盖 sync.Once 单例、goroutine 安全、endpoint 与 region 配置、VPC 端点及调试。
立即学习“go语言免费学习笔记（深入）”；
-
[][][2]int：索引即节点 ID，graph[u]直接拿到所有邻边，无哈希开销 -
map[int][][2]int：需先if _, ok := graph[u]; !ok { continue }，否则 panic - 边权为负？Dijkstra 不适用——此时必须换 Bellman-Ford 或 SPFA，Go 里没现成轮子，得手写
性能瓶颈常卡在堆操作和图遍历顺序上
当图很大（比如 1e5 节点）时，heap.Push 平均 O(log V)，总时间接近 O((V + E) log V)。但实际慢往往是因为：反复分配 Node{} 结构体导致 GC 频繁，或 graph 是指针切片嵌套太深引发 cache miss。
- 把
Node改成[2]int或复用对象池（sync.Pool）可减小分配压力 - 邻接表用一维扁平切片 + offset 数组（类似 CSR 格式）能提升遍历局部性，但编码复杂度上升
- 如果只要两点间最短距离，不是全源，记得在
cur.to == target时直接return cur.dist提前退出
真正难的不是写对算法，而是确认图数据没建错、权重类型没溢出、初始距离没设成 0 导致全图误判为已访问——这些细节比堆逻辑更容易让程序静默失败。
