Go Gonum graph 怎样查询加权图的单源最短路径

在 Go 里查询加权图的单源最短路径，Gonum 的直接做法是用 simple.WeightedDirectedGraph 保存边权，再把源节点交给 path.DijkstraFrom。它返回一个可重复查询的 Shortest 结果：调用 To(targetID) 就能拿到节点序列和累计权重，不需要为每个终点重新跑一遍算法。

官方地址：https://pkg.go.dev/gonum.org/v1/gonum/graph/path

先把边权放进 Gonum 图

示例使用 1 到 5 的有向路线：1→3→2→4→5 的总权重为 9，虽然 1→2 是一条更短的直接边，但继续走到 5 时，完整路线仍要比较后续成本。NewWeightedDirectedGraph 的第一个参数是自环权重，第二个参数是不存在边时的权重；下面用正无穷表示没有这条边。

package main

import (
    "fmt"
    "math"

    "gonum.org/v1/gonum/graph"
    "gonum.org/v1/gonum/graph/path"
    "gonum.org/v1/gonum/graph/simple"
)

func main() {
    // 用正无穷表示不存在的边，避免把缺边误当成零成本。
    g := simple.NewWeightedDirectedGraph(0, math.Inf(1))
    edges := [][3]float64{
        {1, 2, 4}, {1, 3, 2}, {3, 2, 1},
        {2, 4, 5}, {3, 4, 8}, {4, 5, 1}, {2, 5, 10},
    }
    for _, e := range edges {
        // 节点 ID 使用 int64；第三个值是这条有向边的权重。
        from := simple.Node(int64(e[0]))
        to := simple.Node(int64(e[1]))
        g.SetWeightedEdge(g.NewWeightedEdge(from, to, e[2]))
    }

    // 一次构建单源最短路径树，后面可以查询多个目标。
    shortest := path.DijkstraFrom(simple.Node(1), g)
    route, weight := shortest.To(5)
    if route == nil || math.IsInf(weight, 1) {
        fmt.Println("目标不可达")
        return
    }
    fmt.Printf("路径=%v 总权重=%.0f\n", nodeIDs(route), weight)
}

func nodeIDs(nodes []graph.Node) []int64 {
    // 将 Gonum 节点转换为业务层更容易记录的 ID 列表。
    ids := make([]int64, len(nodes))
    for i, n := range nodes {
        ids[i] = n.ID()
    }
    return ids
}

这段代码的预期路径是 [1 3 2 4 5]，权重为 9。这里的输出是根据示例边权推导的阅读结果，不是把插图或页面当作运行证据。

用 DijkstraFrom 查询同一个源点的多个目标

DijkstraFrom 的意义是“从一个源点到所有可达节点的最短路径树”。拿到 Shortest 后，可反复调用 To 或 WeightTo；如果业务需要展示完整路线，用 To，只需要成本时用 WeightTo。

如果一次请求只关心 1 到 5，path.DijkstraFromTo(simple.Node(1), simple.Node(5), g) 更贴近意图；如果同一批请求还要查 2、4、5，就保留一次 DijkstraFrom 的结果，避免重复建树。

负权边和不可达节点要单独处理

Gonum 文档明确说明，DijkstraFrom 遇到从源点可达的负权边会 panic，所以不能把“折扣”“回款”这类可能为负的业务值直接当作 Dijkstra 权重。若图中确实存在负边，应评估 path.BellmanFordFrom；它会额外返回布尔值，用来表示是否发现负环。

不可达目标则是另一类情况：To 得不到有效路线时，不应只判断路径切片长度，还要结合权重是否为正无穷。对于多个同权最短路径，如果要拿到全部候选，使用 DijkstraAllFrom，而不是假设 DijkstraFrom 会保留所有等价路线。

最小验证清单

• 确认图是有向还是无向；方向错误会直接改变可达性。
• 打印路径节点并手算边权总和，核对业务权重是否按同一单位记录。
• 为不可达目标准备降级逻辑，为负权数据在入图前做约束或切换算法。
• 源点固定且目标较多时复用 Shortest；源点变化时重新计算。

常见问题

Gonum 的 DijkstraFrom 能处理负权边吗？

不能把它当作支持负权的算法。只要负权边从源点可达并被发现，文档说明该调用会 panic；这时应改用 Bellman-Ford 或先重新定义非负成本。

为什么 To 返回的路径不是业务上的完整路线名称？

Gonum 只认识节点 ID 和边权。将 ID 映射为城市、服务或仓库名称属于业务层，建议在 nodeIDs 之后单独查表。

只查一个终点还要调用 DijkstraFrom 吗？

可以，但 DijkstraFromTo 能在到达目标后提前结束，更适合单个已知终点；要查多个目标时再使用 DijkstraFrom 复用结果。