Взвешенные пути: релаксация и алгоритм Дейкстры

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

Договор весов и расстояний

Каждое ориентированное ребро хранит стоимость. В нашей лаборатории вес — неотрицательное целое int64. Расстояние складывает веса вдоль пути. До недостижимой вершины расстояние обозначается Infinity=2^63−1; конечные суммы должны быть строго меньше Infinity.

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

Релаксация

Пусть известен путь до u стоимостью d[u], а ребро u→v стоит w. Если d[u]+w < d[v], найден лучший путь до v; обновляем его оценку. Такой шаг называют релаксацией. Пока оценка — стоимость некоторого обнаруженного пути, а не обязательно окончательный минимум.

На графе 0→1 вес 8,0→2 вес 2,2→1 вес 1,1→3 вес 2,2→3 вес 9 сначала d[1]=8,d[2]=2. Обработка 2 улучшает d[1] до 3,d[3] до 11. Обработка 1 улучшает d[3] до 5. Правильные расстояния от 0:0,3,2,5.

Выбираем ближайшую оценку

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

Удобная версия не обновляет уже лежащую запись в куче, а добавляет новую при каждом улучшении. Старые записи позже извлекаются и пропускаются, если сохранённое расстояние не равно текущему d[v]. Это lazy deletion, а не ошибка повторной доставки вершины.

current := heap.Pop(queue).(state)
if current.distance != distance[current.vertex] {
    continue // устаревшая запись
}

Полная реализация и типы очереди находятся в reference/algorithms.go. В отличие от BFS, отмечать вершину окончательно посещённой при первом добавлении нельзя: первая оценка может улучшиться до извлечения.

Числа и стоимость

Перед сложением проверяйте диапазон. В эталоне отвергается weight >= Infinity-currentDistance, поэтому ни переполнение, ни совпадение конечного расстояния с sentinel не прячутся в ответ. Это намеренно строгий договор: даже вычисляемый кандидат вне диапазона вызывает ошибку. Он не обещает обработку произвольных больших весов.

Для V вершин и E рёбер lazy-версия может иметь O(E) записей в куче, время O(V+E log(E+1)), память O(V+E). Часто для простых графов пишут O((V+E)log V); назовите условия, если заменяете одну форму другой. Версия с decrease-key ограничивает число элементов кучи вершинами, но требует дополнительного отображения позиции.

Самостоятельная практика

Напишите Dijkstra с указанным договором и проверьте граф из примера, недостижимую вершину, нулевой вес, параллельные рёбра и отрицательный вес. Отдельно добавьте граф 0→1 вес 10,0→2 вес 1,2→1 вес 1: он обнаружит ошибку «visited при добавлении».

Для небольших графов сравните результат с независимым Bellman-Ford или полным перебором простых путей. Не используйте тот же heap-код как тестовый эталон. На практику — 70 минут.

Критерии готовности: отрицательный вход отвергается; Infinity не складывается; устаревшие записи пропускаются; отсутствие пути отличается от нулевого расстояния; стоимость учитывает количество записей кучи.

Разбор

В контрпримере расстояние до 1 сначала 10, затем 2. Если запретить улучшение после первого открытия, ответ будет неверным. Тест только на дереве такого дефекта не покажет: там до каждой вершины единственный путь.

Источники: Princeton: shortest paths, Go: container/heap.