Go Gonum BellmanFord 遇到负环时怎样报告失败

在 Gonum 中，path.BellmanFordFrom 遇到负环不会返回一个 error，而是通过第二个返回值 ok 报告结果：ok == false 就表示从给定源点可分析到的图中存在负环，最短路结果不能按普通路径使用。官方文档地址：https://pkg.go.dev/gonum.org/v1/gonum/graph/path。

实际接入业务时，先判断 ok，再读取 Shortest.To 做诊断；一旦发现负环，不要把返回的路径和权重当成可结算的最短路，而应向调用方报告“图中存在负环”。

BellmanFordFrom 的失败信号是什么

BellmanFordFrom 的签名是 (path Shortest, ok bool)。ok=true 表示没有检测到负环；ok=false 表示存在负环。这个设计很适合让算法层保留部分诊断信息，同时让业务层明确知道结果不可直接用于正常决策。

这里的负环不是“某一条边权重为负”，而是一个闭环的边权总和小于零。沿着这个环重复走，路径代价还可以继续下降，因此不存在稳定的有限最短路。即使图里还有不受负环影响的节点，也不能忽略全局的失败信号。

先构造一个能暴露负环的图

下面的示例使用一个额外的源点 Q 连接到图中节点，使负环对源点可达。这个做法只服务于示例和诊断；生产代码应根据真实业务入口选择源点，不要为了“让算法看到所有节点”随意改写业务图。

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 := []simple.WeightedEdge{
        {F: simple.Node('a'), T: simple.Node('b'), W: -2},
        {F: simple.Node('b'), T: simple.Node('c'), W: 6},
        {F: simple.Node('c'), T: simple.Node('a'), W: -5},
        {F: simple.Node('a'), T: simple.Node('f'), W: 2},
    }
    for _, edge := range edges {
        // 统一把带权边写入有向图，负环由 a->b->c->a 形成。
        g.SetWeightedEdge(edge)
    }

    // 增加一个零成本源点，让示例中的负环对 Bellman-Ford 可达。
    for _, node := range graph.NodesOf(g.Nodes()) {
        g.SetWeightedEdge(simple.WeightedEdge{F: simple.Node('Q'), T: node})
    }

    tree, ok := path.BellmanFordFrom(simple.Node('Q'), g)
    if !ok {
        // ok=false 是算法级失败信号，不要把 tree 当作普通最短路结果。
        fmt.Println("图中存在负环，停止使用最短路结果")
        _ = tree
        return
    }
    fmt.Println("没有检测到负环")

注意，ok 不是“是否找到某个目标节点”的标志，而是 Bellman-Ford 是否能为这次分析提供合法的最短路树。代码中可以把它转换成项目自己的错误，例如 ErrNegativeCycle，再由 HTTP 层、任务队列或结算服务决定如何处理。

用 Shortest.To 找到受影响的节点

当 ok=false 时，返回的 Shortest 仍可用于诊断。对目标节点调用 To 会得到路径和权重；如果路径受到负环影响，权重会是负无穷。路径只适合写入日志或诊断响应，不能作为最终配送、路由或计费依据。

func reportNegativeCycle(tree path.Shortest, ids []int64) {
    for _, id := range ids {
        nodes, weight := tree.To(id)
        if math.IsInf(weight, -1) {
            // -Inf 表示到该节点的路径受负环影响，必须从正常结果中剔除。
            fmt.Printf("节点 %d 受负环影响，诊断路径=%v\n", id, nodes)
            continue
        }
        // 没有被负环污染的节点也只作为诊断信息输出。
        fmt.Printf("节点 %d 的诊断路径=%v，权重=%v\n", id, nodes, weight)
    }
}

官方文档还特别提醒，负环路径的权重不能代表真实最短路径；因此不要只检查 len(nodes)，也不要只看路径最后一个节点。正确的最低判断是先处理 ok=false，再用 math.IsInf(weight, -1) 标记具体受影响节点。

怎样向上层报告才不会误导调用方

推荐把算法结果分成两条通道：

• 正常通道：只有 ok=true 时，才返回可用于业务决策的路径和有限权重。
• 失败通道：ok=false 时返回稳定的负环错误码，同时把受影响节点、诊断路径和图版本写入日志或可观测事件。

如果接口必须返回部分结果，也应把它们标记为诊断数据，避免调用方误以为“某些节点仍然有可靠最短路”。在重试前先修复图数据或权重规则；盲目重试同一张图只会重复得到失败。

和 FloydWarshall 怎样选择

BellmanFordFrom 适合从一个源点出发，判断可达范围内是否有负环，复杂度为 O(|V|·|E|)。如果需要更全面地分析哪些节点处在负环中、哪些点对之间的路径受负环影响，可以考虑 path.FloydWarshall。它返回的布尔值同样用于表示是否存在负环，并可通过节点到自身的权重是否为负无穷辅助定位。

选择时可以记住：单源任务优先 Bellman-Ford；需要全图关系分析时再考虑 Floyd-Warshall。后者复杂度为 O(|V|³)，图规模扩大后成本会明显上升。

常见问题

有一条负权边就一定失败吗？

不是。Bellman-Ford 可以处理负权边，只有可达的负环才会让最短路没有稳定有限解。

ok=false 后还能调用 To 吗？

可以用于诊断，但不能把返回值当作正常最短路。重点检查负无穷权重，并在业务边界阻止继续结算。

为什么不直接改用 Dijkstra？

Dijkstra 不适合存在负权边的图；如果业务能够保证所有边权非负，才应改用 Dijkstra，并在输入层明确维护这个约束。

总结一下：Gonum 的 Bellman-Ford 通过 ok bool 报告负环，而不是返回 Go error。先处理这个全局失败信号，再用 Shortest.To 和 math.IsInf 做节点级诊断，最后把诊断数据和可用业务结果严格分开。