クラウド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 {
}

ここでは保守的な方針を採用しています。実際に実行した緩和計算でオーバーフローが発生した時点で、その問い合わせ全体を失敗とします。グラフ内により短い別の経路があっても処理は継続しません。本番実装で異なる方針を採る場合は、別途契約を定義する必要があり、両者のエラー時の挙動をそのまま比較することはできません。

答えだけでなく性質も検証する

固定の期待値に加え、3種類の変換を検証します。各頂点の辺の順序を入れ替えても、距離は変わらないこと。既存の辺より重みが大きい重複辺を追加しても、結果が短くならないこと。元のグラフと接続していない有効な部分グラフを追加しても、既存の頂点の結果が変わらないことです。これらの距離の性質を検証するテストでは、関係するすべての加算結果が表現可能な範囲に収まるよう、重みの範囲を制限します。

こうした性質の検証では、入力順序への依存や、並行辺を誤って上書きする処理などの不具合を見つけられます。ランダムな小規模グラフを生成する場合は、乱数シードを固定し、失敗時には隣接リスト全体、始点、期待値を保存します。再現が難しい失敗番号だけを記録してはいけません。

本番のインターフェースが経路も返す場合は、さらに辺を1本ずつたどって検証する必要があります。始点と終点が正しいこと、すべての辺が実在すること、重みの合計が距離に一致することを確認します。並行辺がある場合は、頂点列だけでなく辺の識別子を返すのが望ましい設計です。同じ最短距離の経路は複数あり得るため、特定の前駆頂点列との一致を強制しないでください。

クラウドノードの受け入れ検証に組み込む

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 を使ったりしないでください。実際のプロジェクトでは、同じサンプル群をテストターゲットに組み込み、本番用の経路計算のエントリーポイントを呼び出します。

パイプラインでは、少なくとも失敗したグラフ、ツールチェーンのバージョン、実際に得られた距離の配列を保存します。検証の順序は、入力の妥当性、距離の結果、経路の再検証、性能予算とします。正しさのチェックを通過してから、大規模グラフの処理時間を別途計測してください。一度「高速に動いた」ことを理由に、到達不能やオーバーフローの扱いの誤りを見逃さないためです。

よくある質問