云端 Mac 上的 iOS 最短路径验收：非负权重、不可达与溢出

离线导航、园区路线和应用内流程规划，都可能把最短路径计算放进 iOS 客户端。普通样本能算出距离，遇到零权环、断开的节点或超大权重，却可能返回看似合理的错误结果。在云端 Mac 上建立一份小而清楚的 Swift 参考实现，比只对着界面点选路线更容易定位算法回归。

先固定图与结果的契约

本文使用有向图，顶点编号从零开始，边权为非负 Int64。无向道路需要显式添加两个方向的边。起点到自身距离为零，不可达节点返回 nil；不能拿零或最大整数充当不可达标记。

输入入口必须检查起点、边终点和负权，包括起点无法访问到的子图。平行边允许存在，让算法选择较短的一条；自环也允许，但不能因此无限更新。

Dijkstra 依赖非负权重。不要通过把负数改成零来“修复”输入，那会改变业务问题本身。

业务若以米、毫秒等整数单位建图，应在数据转换处确定精度。不要先用浮点数算距离，再临时截断成整数，否则测试比较的已不是同一份图。

写一份容易审查的参考模型

下面实现采用逐个扫描顶点的方式，复杂度为 O(V²＋E)，空间复杂度为 O(V)。它适合小图验收，不用于证明生产算法在大型地图上的性能。将代码保存为 shortest-path.swift，后续样本追加到同一文件。

enum GraphError: Error {
    case invalidVertex
    case negativeWeight
    case overflow
}

struct Edge {
    let to: Int
    let weight: Int64
}

func distances(
    _ graph: [[Edge]],
    from source: Int
) throws -> [Int64?] {
    guard graph.indices.contains(source) else {
        throw GraphError.invalidVertex
    }

    for edges in graph {
        for edge in edges {
            guard graph.indices.contains(edge.to) else {
                throw GraphError.invalidVertex
            }
            guard edge.weight >= 0 else {
                throw GraphError.negativeWeight
            }
        }
    }

    var result = Array<Int64?>(repeating: nil, count: graph.count)
    var settled = Array(repeating: false, count: graph.count)
    result[source] = 0

    for _ in graph.indices {
        var selected: Int?
        for vertex in graph.indices where !settled[vertex] {
            guard let value = result[vertex] else { continue }
            if let current = selected {
                if value < result[current]! {
                    selected = vertex
                }
            } else {
                selected = vertex
            }
        }

        guard let vertex = selected else { break }
        settled[vertex] = true
        let base = result[vertex]!

        for edge in graph[vertex] where !settled[edge.to] {
            let (candidate, overflow) =
                base.addingReportingOverflow(edge.weight)
            guard !overflow else { throw GraphError.overflow }

            if let previous = result[edge.to] {
                if candidate < previous {
                    result[edge.to] = candidate
                }
            } else {
                result[edge.to] = candidate
            }
        }
    }

    return result
}

这个模型只返回距离，不维护前驱，避免把路径重建问题混进距离验收。同距离顶点按编号先后处理，便于复现，但业务不应依赖这一顺序。

用固定样本压住边界

先加入一张包含平行边、零权环和孤立节点的小图。预期结果直接写出来，不要调用另一份待测算法生成答案。

let graph: [[Edge]] = [
    [Edge(to: 1, weight: 9), Edge(to: 1, weight: 2)],
    [Edge(to: 2, weight: 0)],
    [Edge(to: 1, weight: 0), Edge(to: 3, weight: 3)],
    [],
    []
]

let actual = try distances(graph, from: 0)
precondition(actual == [0, 2, 2, 5, nil])

let singleton = try distances([[]], from: 0)
precondition(singleton == [0])

再分别增加空图、越界起点、负权边、越界终点，以及合法最大距离。每个错误样本应单独断言具体错误类型，避免把任意异常都当成通过。

let largest = try distances([
    [Edge(to: 1, weight: Int64.max)],
    []
], from: 0)
precondition(largest[1] == Int64.max)

do {
    _ = try distances([
        [Edge(to: 1, weight: Int64.max)],
        [Edge(to: 2, weight: 1)],
        []
    ], from: 0)
    preconditionFailure("Expected overflow")
} catch GraphError.overflow {
}

这里采用保守策略：实际执行的松弛计算一旦溢出，整次查询失败，即使图中另有较短路线也不继续。生产实现若采用不同策略，需要另写契约，不能直接比较两者的错误行为。

检查性质，不只检查几个答案

固定答案之外，再验证三类变换。打乱每个顶点的边顺序，距离不应改变；添加一条权重更大的重复边，不应改善结果；添加一个与原图断开的合法子图，原有顶点的结果应保持不变。这些距离性质测试应限制权重范围，确保所有相关加法均可表示。

这些性质能发现依赖输入顺序、错误覆盖平行边等缺陷。若生成随机小图，应固定随机种子，并在失败时保存完整邻接表、起点和期望结果，不能只记录一个难以重放的失败编号。

如果生产接口还返回路线，必须额外逐边回放：确认起终点正确、每条边确实存在、权重之和等于距离。存在平行边时最好返回边标识，而不只是顶点序列。同样短的路线可以不同，不要强行比较某一条前驱链。

接入云端节点的验收入口

在 VMFly 物理节点上，先记录工具链，再编译运行。以下命令不依赖模拟器，适合放在完整应用构建之前。

set -eu
xcrun swiftc --version
mkdir -p .build
xcrun swiftc -Onone shortest-path.swift \
  -o .build/shortest-path-check
.build/shortest-path-check

示例使用 precondition 让错误结果以非零状态退出，不要换成发布优化可能移除的 assert，也不要使用会删除这些检查的 -Ounchecked。正式工程再将同一批样本接入测试目标，调用生产路径计算入口。

流水线至少保留失败图、工具链版本和实际距离数组。验收顺序保持为输入合法性、距离结果、路径回放、性能预算。正确性门禁通过后，再单独测量大图耗时，避免用一次“跑得很快”掩盖不可达或溢出语义错误。

常见问题