Go Gonum 最短路径结果怎样区分不可达与零距离

Go Gonum 查询最短路径时，不能用 weight == 0 判断“没有路径”。对 path.Shortest 来说，源节点本身和真正的零成本路径都可能得到权重 0；不可达或未被当前最短路对象收录的节点，则会得到空路径与正无穷。稳妥的判断顺序是先看路径是否为空，再用 math.IsInf(weight, 1) 识别不可达。

官方资料：https://pkg.go.dev/gonum.org/v1/gonum/graph/path

把“没有路径”和“路径成本为零”分开：nil, +Inf 表示不可达语义，非空路径配合 0 才表示零成本可达。

先看 To 的返回契约

path.DijkstraFrom、path.BellmanFordFrom 和 path.AStar 都会返回一个 Shortest。调用 Shortest.To(vid) 时，正常结果是路径切片和路径权重；如果目标 ID 不存在，或者目标在当前搜索范围内的距离仍是正无穷，Gonum 返回 nil 与 math.Inf(1)。

WeightTo(vid) 只返回权重，未知 ID 同样返回正无穷。因此，只打印权重很容易把“不可达”误认为一个普通数值边界；业务层至少要同时保留路径状态。

零成本路径为什么不是不可达

最短路径的“成本”与“是否存在路径”是两件事。假设边权可以为零，s -0-> t 仍然是一条有效路径，返回的路径应包含节点，权重为 0。源节点到自身也以距离 0 初始化，通常会得到只包含源节点的路径。

相反，不可达目标的路径是 nil，权重是 +Inf。所以判断时不要只写 if weight == 0，也不要只写 if len(nodes) == 0 而忽略负环等特殊结果。

package main

import (
    "fmt"
    "math"

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

// classifyPath 把 Gonum 的返回值转换为业务层容易处理的状态。
func classifyPath(p path.Shortest, target int64) (string, []int64, float64) {
    nodes, weight := p.To(target)

    // 空路径加正无穷表示当前对象没有可达路径。
    if nodes == nil && math.IsInf(weight, 1) {
        return "unreachable", nil, weight
    }

    ids := make([]int64, 0, len(nodes))
    for _, node := range nodes {
        // 保留节点 ID，避免业务层依赖具体 Node 实现。
        ids = append(ids, node.ID())
    }
    if weight == 0 {
        // 非空路径的零权重才是零成本可达。
        return "reachable-zero-cost", ids, weight
    }
    return "reachable", ids, weight
}

func useResult(p path.Shortest, target int64) {
    // 统一从分类结果进入日志或接口响应，避免散落比较 float64。
    state, ids, weight := classifyPath(p, target)
    fmt.Println(state, ids, weight)
}

这里的关键不是把所有结果都包装成字符串，而是把 Gonum 的两个返回值作为一个整体处理：路径负责说明“有没有具体节点链路”，权重负责说明成本或特殊值。

未知节点和已知但不连通的节点有什么区别

从调用者的角度看，未知 ID 和已在图中、但从源节点不可达的 ID，可能都会呈现为 nil, +Inf。这正是最容易被忽略的边界。

当传入的是完整的 graph.Graph，Gonum 会把图中的节点放入最短路径对象，未连通节点保留正无穷距离；如果传入的是更窄的遍历接口，最短路径对象可能只保存从源节点实际遍历到的节点。也就是说，To 的返回值适合回答“当前路径对象能否给出一条路”，不一定能回答“这个 ID 是否存在于原始图”。

如果业务需要区分两者，应在查询前从原始图维护节点存在性：

package main

import (
    "fmt"

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

// lookup 先判断节点是否存在，再解释最短路径结果。
func lookup(g graph.Graph, shortest path.Shortest, target int64) {
    if g.Node(target) == nil {
        // 节点根本不在原图中，不能和已知但不可达混为一谈。
        fmt.Println("unknown-node")
        return
    }
    nodes, weight := shortest.To(target)
    if nodes == nil {
        // 节点存在，但当前源节点没有到达它的路径。
        fmt.Println("known-but-unreachable", weight)
        return
    }
    fmt.Println("reachable", len(nodes), weight)
}

负权和负环不能套用普通不可达判断

DijkstraFrom 适用于非负边权；官方实现遇到从源节点可达的负边会触发 panic。若图允许负边，应考虑 BellmanFordFrom 或其他适配算法，并处理它们的负环语义。

当最短路径经过负环时，某些结果会出现 -Inf。这不是“路径不存在”，而是成本可以沿负环继续下降，已经失去有限的最短值。分类逻辑应把 +Inf、-Inf 和有限数分开：

package main

import (
    "math"
)

// classifyWeight 只解释特殊权重，不代替 To 的路径判断。
func classifyWeight(weight float64) string {
    if math.IsInf(weight, 1) {
        return "unreachable-or-not-recorded"
    }
    if math.IsInf(weight, -1) {
        return "negative-cycle-impact"
    }
    if weight == 0 {
        return "finite-zero-cost"
    }
    return "finite-cost"
}

注意，+Inf 只能说明当前最短路径对象没有提供有限路径；若要区分未知节点、已知不可达节点，还要结合原图节点集合。

把结果判断收敛成一条小规则

面对 Shortest.To 的结果，可以按下面的顺序写业务判断：

1. 先判断路径是否为 nil，不要先把权重当作布尔信号。
2. 路径为空时，再用 math.IsInf(weight, 1) 识别不可达或未被当前对象记录。
3. 路径非空且权重为 0，表示源节点自身或一条零成本可达路径。
4. 权重为 -Inf 时转入负环处理，不要显示为“没有路线”。
5. 若接口需要区分未知 ID 与已知不可达，查询原始 graph.Graph.Node 或保存独立节点索引。

一句话总结：在 Gonum 中，0 是一个合法的有限路径成本，+Inf 才是不可达方向的信号，而“未知节点”和“已知但不连通”是否能分开，需要由原始图的节点集合补充语义。

相关问题

源节点查询自己为什么通常是 0？

最短路径对象会把源节点的初始距离设为 0，因此源节点到自身不是不可达，而是零成本的平凡路径。

只调用 WeightTo 能判断路径存在吗？

可以识别有限值与正无穷，但无法直接得到路径节点，也更难处理业务需要的节点链路。需要路线时应调用 To。

为什么未知节点和不可达节点看起来一样？

两者都可能让当前最短路径对象没有对应的有限距离。要区分它们，必须回到原始图或业务自己的节点目录判断 ID 是否存在。