Проверка кратчайших путей в iOS: веса, недостижимость и переполнение

Офлайн-навигация, маршруты по территории кампуса и планирование последовательности действий внутри приложения — всё это может требовать расчёта кратчайших путей на стороне iOS-клиента. На обычных примерах расстояния вычисляются верно, но циклы нулевого веса, недостижимые вершины или очень большие веса способны привести к правдоподобным, но неверным результатам. Небольшая и понятная эталонная реализация на Swift, запущенная на облачном Mac, помогает локализовать регрессии алгоритма лучше, чем одна лишь проверка маршрутов через интерфейс.

Сначала определите контракт графа и результатов

В этой статье используется ориентированный граф с нумерацией вершин с нуля и неотрицательными весами рёбер типа Int64. Для дороги с двусторонним движением нужно явно добавить рёбра в обоих направлениях. Расстояние от начальной вершины до неё самой равно нулю, а для недостижимой вершины возвращается nil. Ни ноль, ни максимальное целое число нельзя использовать как признак недостижимости.

На входе необходимо проверять начальную вершину, конечные вершины всех рёбер и отсутствие отрицательных весов, в том числе в подграфах, недостижимых из начальной вершины. Параллельные рёбра допустимы: алгоритм должен выбрать более короткое. Петли тоже разрешены, но не должны вызывать бесконечные обновления.

Алгоритм Дейкстры требует неотрицательных весов. Не «исправляйте» входные данные заменой отрицательных значений на ноль: это меняет саму прикладную задачу.

Если граф строится в целочисленных единицах, например метрах или миллисекундах, точность нужно определить на этапе преобразования данных. Нельзя сначала вычислять расстояния в числах с плавающей точкой, а затем по месту отбрасывать дробную часть: в таком случае тесты сравнивают уже не один и тот же граф.

Напишите эталонную модель, которую легко проверить

В реализации ниже вершины выбираются последовательным просмотром. Временная сложность — 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 {
}

Здесь принята консервативная политика: если при фактически выполняемой релаксации возникает переполнение, весь запрос завершается ошибкой. Вычисления не продолжаются, даже если в графе есть другой, более короткий путь. Если рабочая реализация использует иную политику, для неё нужен отдельный контракт: напрямую сравнивать поведение двух реализаций при ошибках нельзя.

Проверяйте свойства, а не только отдельные ответы

Помимо фиксированных ответов проверьте три вида преобразований. Перестановка рёбер в списке каждой вершины не должна менять расстояния. Добавление дублирующего ребра с большим весом не должно улучшать результат. Добавление корректного подграфа, не связанного с исходным, должно оставлять результаты для прежних вершин неизменными. В таких тестах свойств расстояний нужно ограничивать диапазон весов, чтобы результаты всех задействованных сложений оставались представимыми.

Эти свойства помогают обнаружить зависимость от порядка входных данных, ошибочное перезаписывание параллельных рёбер и подобные дефекты. При генерации случайных небольших графов фиксируйте начальное значение генератора случайных чисел, а при сбое сохраняйте полный список смежности, начальную вершину и ожидаемый результат. Одного номера неудачного теста, по которому трудно воспроизвести сбой, недостаточно.

Если рабочий интерфейс возвращает ещё и маршрут, его необходимо дополнительно проверить по каждому ребру: убедиться, что начальная и конечная вершины верны, каждое ребро действительно существует, а сумма весов равна расстоянию. При наличии параллельных рёбер лучше возвращать идентификаторы рёбер, а не только последовательность вершин. Кратчайших путей одинаковой длины может быть несколько, поэтому не требуйте совпадения с одной конкретной цепочкой предшественников.

Подключите проверку к CI на облачном узле

На физическом узле 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, удаляющий эти проверки. В реальном проекте подключите тот же набор примеров к тестовой цели и вызывайте рабочую точку входа для расчёта маршрутов.

В конвейере нужно сохранять как минимум граф, на котором произошёл сбой, версию набора инструментов и фактический массив расстояний. Соблюдайте порядок проверок: корректность входных данных, результаты расчёта расстояний, проверка маршрута по рёбрам, соответствие бюджету производительности. Только после прохождения проверок корректности отдельно измеряйте время работы на больших графах. Иначе один «быстрый запуск» может скрыть ошибки в обработке недостижимости или переполнения.

Часто задаваемые вопросы