Test iOS shortest paths: nonnegative weights, reachability and overflow

Offline navigation, campus routing and in-app workflow planning may all require shortest-path calculations in an iOS client. An implementation can produce correct distances for ordinary examples yet return plausible-looking wrong answers when faced with zero-weight cycles, disconnected vertices or very large weights. A small, readable Swift reference implementation on a cloud Mac makes algorithm regressions easier to pinpoint than testing routes through the UI alone.

Define the graph and result contract first

This article uses a directed graph with zero-based vertex indices and nonnegative Int64 edge weights. For an undirected road, explicitly add an edge in each direction. The distance from the source to itself is zero, and unreachable vertices return nil; neither zero nor the maximum integer value should serve as an unreachable marker.

The input boundary must validate the source vertex, every edge destination and all weights, including those in subgraphs that cannot be reached from the source. Parallel edges are allowed: the algorithm should choose the shorter one. Self-loops are also allowed, but must not cause endless updates.

Dijkstra’s algorithm requires nonnegative weights. Do not “fix” input by replacing negative values with zero; that changes the problem you are trying to solve.

If your application builds a graph using integer units such as meters or milliseconds, establish the precision during data conversion. Do not calculate distances in floating point and then truncate them to integers at the last minute: the tests would no longer be comparing the same graph.

Write a reference model that is easy to review

The implementation below scans vertices one at a time, with O(V²＋E) time complexity and O(V) space complexity. It is suitable for correctness checks on small graphs, not for demonstrating the production algorithm’s performance on large maps. Save the code as shortest-path.swift and append the later examples to the same file.

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
}

This model returns only distances and does not track predecessors, keeping path reconstruction separate from distance validation. Vertices with equal distances are processed in index order for reproducibility, but application logic should not depend on that ordering.

Cover edge cases with fixed fixtures

Start with a small graph containing parallel edges, a zero-weight cycle and an isolated vertex. Write the expected results explicitly rather than generating them with another algorithm that also needs testing.

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])

Next, add separate cases for an empty graph, an out-of-range source, a negative-weight edge, an out-of-range destination and the largest valid distance. Each invalid-input case should assert the specific error, rather than treating any thrown error as a pass.

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 {
}

This implementation takes a conservative approach: if any relaxation calculation actually performed overflows, the entire query fails, even if the graph contains a shorter alternative route. If the production implementation uses a different policy, document that contract separately; the two implementations’ error behavior cannot be compared directly.

Check properties, not just a few answers

Beyond fixed expected results, verify three kinds of transformations. Shuffling each vertex’s outgoing edges must not change the distances. Adding a duplicate edge with a larger weight must not improve any result. Adding a valid subgraph disconnected from the original graph must leave the results for the original vertices unchanged. Constrain the weight range in these distance-property tests so that every relevant addition is representable.

These properties can expose defects such as dependence on input order or incorrectly overwriting parallel edges. If you generate random small graphs, use a fixed random seed. On failure, save the complete adjacency list, source vertex and expected results—not just a failure ID that is difficult to reproduce.

If the production API also returns a route, validate it edge by edge: check that the endpoints are correct, every edge exists and the sum of the weights equals the reported distance. When parallel edges exist, returning edge identifiers is preferable to returning only a vertex sequence. Equally short routes may differ, so do not require a match against one particular predecessor chain.

Add a validation entry point on the cloud node

On a VMFly physical node, record the toolchain first, then compile and run the checks. The following commands do not require a simulator and are suitable for running before a full application build.

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

The example uses precondition so that incorrect results cause a nonzero exit status. Do not replace it with assert, which may be removed by release optimizations, or use -Ounchecked, which removes these checks. In the actual project, add the same fixtures to a test target and call the production path-calculation entry point.

At a minimum, the pipeline should retain the failing graph, toolchain version and actual distance array. Keep the validation order consistent: input validity, distance results, route validation, then performance budget. Once the correctness gate passes, measure large-graph runtime separately. A single “it ran fast” result must not hide incorrect reachability or overflow semantics.

Frequently asked questions