雲端 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。正式專案則應將同一批測試案例接入測試目標，呼叫正式的路徑計算入口。

流水線至少要保留失敗的圖、工具鏈版本與實際距離陣列。驗收順序應維持為輸入合法性、距離結果、路徑回放、效能預算。通過正確性檢查後，再獨立量測大型圖的執行時間，避免用一次「跑得很快」掩蓋無法到達或溢位的語意錯誤。

常見問題