Go Gonum graph 怎样取得多条候选最短路径

我第一次把“最短路径”接到路线推荐里时，真正麻烦的不是找到第一条路，而是用户会继续问：如果这条路拥堵，还有哪些相近的走法？Gonum 的 YenKShortestPaths 正好处理这个问题：它返回从起点到终点的多条不含环候选路径，并允许用数量和相对代价范围控制结果。

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

这类结果和“所有等长最短路径”不是一回事。它更像一个候选集：第一条通常最省，后面的路径可以略贵，但仍在你接受的范围内。下面用一个带权有向图说明完整写法。

先分清：要的是候选路线，不是最短路树

如果只想知道某个起点到终点的一条最短路径，DijkstraFromTo 更直接；如果要一次得到所有节点之间的最短路信息，可以看 AllShortest 相关 API。当前问题的关键是“按顺序拿几条替代路线”，所以使用 Yen 算法封装更合适。

我在设计接口时会先固定三个业务条件：

• 候选路径是否允许重复节点？这里选择不允许，也就是 loopless。
• 最多需要几条？这个值对应 k，不是必须返回的条数。
• 路线比第一条多花多少仍可接受？这个范围对应 cost。

用带权有向图表达路线成本

graph/path 接收的是 Gonum 的图接口。示例使用 simple.NewWeightedDirectedGraph，把每条有向边的权重当成距离、时间或综合成本。为了让结果稳定可解释，示例只放非负权重；官方文档明确说明 YenKShortestPaths 遇到负权边会 panic。

package main

import (
    "fmt"
    "math"

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

func main() {
    // absent 用正无穷表示没有边，路线权重保持非负。
    g := simple.NewWeightedDirectedGraph(0, math.Inf(1))
    edges := []struct {
        from, to int64
        weight   float64
    }{
        {from: 1, to: 2, weight: 1},
        {from: 2, to: 5, weight: 2},
        {from: 1, to: 3, weight: 2},
        {from: 3, to: 5, weight: 2},
        {from: 1, to: 4, weight: 3},
        {from: 4, to: 5, weight: 2},
        {from: 2, to: 3, weight: 1},
    }
    for _, edge := range edges {
        // SetWeightedEdge 同时表达方向和业务成本。
        from := simple.Node(edge.from)
        to := simple.Node(edge.to)
        g.SetWeightedEdge(g.NewWeightedEdge(from, to, edge.weight))
    }

    // 这里请求最多 3 条，允许候选路径比最短路多 2 个成本单位。
    paths := path.YenKShortestPaths(g, 3, 2, simple.Node(1), simple.Node(5))
    for index, nodes := range paths {
        // graph.Node 只保证 ID；业务展示可在这一层转换成自己的名称。
        fmt.Printf("候选 %d: %v\n", index+1, nodeIDs(nodes))
    }
}

func nodeIDs(nodes []graph.Node) []int64 {
    // 保留节点顺序，便于调用方继续计算或渲染路线。
    ids := make([]int64, 0, len(nodes))
    for _, node := range nodes {
        ids = append(ids, node.ID())
    }
    return ids
}

关键点是：先把边写进图，再把起点和终点作为 graph.Node 传入算法；辅助函数只依赖节点接口，不强行断言成某个具体实现。

k 和 cost 怎么配，决定候选集是否有用

k 是最多返回多少条候选路径，不代表一定能拿到这么多条。如果图里只有一条可行路线，结果自然少于 k。当 k 为负数时，官方 API 会只使用代价上限来限制结果数量，这种用法适合“预算范围内尽量多找”的场景，但调用方仍应设置合理的成本边界。

cost 表示相对于最短路径可接受的额外代价范围。比如最短路径代价为 3，允许额外 2，那么候选的总成本上限可以理解为 5。这里不要把它当成“第 k 条路径的固定成本”，也不要直接拿用户预算去替代路线成本模型。

读取结果时不要假设一定有 k 条

返回值是 [][]graph.Node。最外层代表候选路径，内层是从起点到终点的节点序列。生产代码里我通常会先判断长度，再把节点 ID 转成业务对象；如果结果为空，就把“没有满足条件的路径”作为正常分支处理，而不是访问 paths[0]。

func describeCandidates(paths [][]graph.Node) {
    // 空切片表示当前条件下没有可返回的候选路径。
    if len(paths) == 0 {
        fmt.Println("没有满足代价范围的路径")
        return
    }

    for i, nodes := range paths {
        // 每条路径都保留节点顺序，方便映射成站点或路段。
        ids := make([]int64, 0, len(nodes))
        for _, node := range nodes {
            ids = append(ids, node.ID())
        }
        fmt.Printf("候选 %d: %v\n", i+1, ids)
    }
}

还要注意一个容易被忽略的事实：这个 API 返回路径节点，但没有把每条路径的总权重作为单独返回值给出。若业务需要展示“总耗时”或“总里程”，应使用原图的边权按相邻节点重新累加，并把节点不存在、边不存在等异常作为数据问题处理。

哪些情况下不适合直接套用

第一，图中存在负权边时不要把错误留给线上调用；官方文档明确说明该函数会 panic。第二，若业务需要允许回到已经经过的节点，那就不是 loopless 候选路径问题，需要重新定义路径约束。第三，候选数量和允许代价同时放得很大时，搜索空间会变宽，应该从较小的 k 和成本范围开始，再根据真实请求量调整。

如果图没有实现加权接口，Gonum 会使用统一代价，这意味着算法只按边数比较，而不是按业务里的距离或时间比较。这个默认行为很方便，也很容易让路线结果和产品预期不一致。

我的判断清单

• 要一条最短路：优先考虑 DijkstraFromTo。
• 要多条不重复节点的候选路：使用 YenKShortestPaths。
• 要所有等长最短路径：另看 AllShortest.AllBetween，不要混用概念。
• 图有负权边：先修正成本模型或更换算法，不要直接调用。
• 结果数量不足：先判断是否真的存在更多满足 cost 范围的路线。

对我来说，Yen 的价值不在于把“最短”三个字变成更多结果，而在于给路线推荐一个有条件的替代集：先保证路径约束明确，再用 k 和相对成本控制产品愿意展示的范围。这样得到的候选才不会只是算法输出，而是能被业务解释的路线选择。

常见问题

Gonum 的 YenKShortestPaths 会返回重复节点的路径吗？

它返回 loopless paths，也就是不含环的路径。若业务允许循环访问节点，应选用不同的路径定义。

k 比实际可行路线多会报错吗？

不会因为候选不足就报错，返回的路径数量可以小于 k；调用方需要按切片长度处理。

为什么没有传入权重函数？

权重来自 Gonum 图的加权接口；如果图没有实现加权能力，路径包会按统一代价处理。要体现时间或距离，应构造带权图。