Конспект: кратчайшие пути и Дейкстра

Понятия

Вес ребра - число на нём; длина пути - сумма весов. dist[v] - оценка СВЕРХУ кратчайшего расстояния, только уменьшается. prev[v] - откуда пришли, по нему восстанавливают маршрут.

Релаксация - единственная операция всех алгоритмов раздела:

если dist[u] + w(u, v) < dist[v]:  dist[v] = dist[u] + w(u, v);  prev[v] = u

Оптимальная подструктура - любой кусок кратчайшего пути сам кратчайший; поэтому путь можно собирать по частям.

Дейкстра - брать необработанную вершину с наименьшей оценкой, фиксировать её и релаксировать её рёбра.

Круг Дайала - при целых весах 1..C очередь Дейкстры лежит в окне [d, d + C], хватает C + 1 корзины по остатку; O(E + C + D), где D - наибольший вставленный ключ, в том числе устаревший. Поразрядная куча - корзины ширины 1, 1, 2, 4, …; первая непустая делится при опустошении нижней. Единственная запись вершины, удаление за O(1) и поиск новой корзины от старого номера вниз дают O(E + V·log(C+1)).

Что унести

Алгоритмы отличаются только ПОРЯДКОМ релаксаций, а не самой операцией.

Корректность Дейкстры (учить как рассуждение, а не как факт): пусть до извлечённой вершины u есть путь короче dist[u]. На нём найдётся первое ребро x → y из обработанного множества наружу; при обработке x мы его релаксировали, значит dist[y] <= длина куска до y. Остаток пути неотрицателен, значит длина всего пути >= dist[y], откуда dist[y] < dist[u] - противоречие с выбором u как минимума.

неотрицательность весов нужна ровно в одном месте: «остаток пути ≥ 0»

Ленивая реализация: при каждом улучшении кладём в кучу новую пару (dist[u], u), а устаревшие отбрасываем проверкой if d > dist[v]: continue. Записей до E, код короткий - так и пишут.

Тихие ошибки: обход в ширину на взвешенном графе (ответ правдоподобный, но неверный); забытая проверка устаревших записей; heappush(q, v) без оценки (куча сравнивает номера вершин); Дейкстра на отрицательных весах «потому что обычно работает»; попытка сдвинуть все веса на константу - добавка умножается на число рёбер и меняет ответ.

Куда это ведёт

Следующая глава - отрицательные веса: Беллман-Форд, кратчайшие пути на ДАГе по топологическому порядку и обнаружение отрицательных циклов, после которых задача теряет смысл.