Кратчайшие пути: постановка задачи и релаксация

Если ты знаешь три постановки задачи, понимаешь релаксацию и свойство оптимальной подструктуры и можешь объяснить, почему обход в ширину ломается на разных весах, листай до «Теперь сам».

Как думаешь, почему обход в ширину перестаёт работать

Обход в ширину находит кратчайшие пути в невзвешенном графе - это мы разобрали. Прежде чем читать дальше, подумай: что произойдёт, если у рёбер появятся разные длины? Возьми две вершины, соединённые прямым ребром длины 10, и обходной путь из двух рёбер по 1. Что вернёт обход в ширину и почему?

На что это похоже

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

Механизм: веса, релаксация и три постановки

вес ребра w(u, v)     - число на ребре: длина, время, стоимость
длина пути            - СУММА весов его рёбер
dist[v]               - текущая ОЦЕНКА СВЕРХУ кратчайшего расстояния от старта до v
                        (в начале dist[старт] = 0, у всех остальных +∞)

релаксация ребра u → v:
    если dist[u] + w(u, v) < dist[v]:
        dist[v] = dist[u] + w(u, v)        # нашли путь подешевле
        prev[v] = u                        # запомнили, откуда пришли

Две оговорки о записи, чтобы потом не спотыкаться. Первая: w(u, v) - это ОБОЗНАЧЕНИЕ веса ребра u → v, а не функция, которую надо написать; в коде вес обычно лежит в самом списке рёбер или в списке смежности, и вместо w(u, v) там стоит wt[e]. Вторая: +∞ в коде не наберёшь. Берут заведомо большое число - такое, что настоящий путь до него не дотянется:

INF = 1000000        # больше суммы всех весов графа
dist = [INF] * V     # у всех оценка «пока не добрались»
dist[start] = 0

INF - это просто число, поэтому «бесконечность плюс вес» тоже число, и его можно случайно улучшить: INF + (−5) < INF. Отсюда правило, которое встретится в каждом алгоритме раздела: релаксировать рёбра только из вершины, до которой УЖЕ добрались, то есть при dist[u] < INF.

Оценка сверху значит вот что: dist[v] - это длина какого-то НАСТОЯЩЕГО пути до v, который мы уже нашли. Кратчайший путь может быть только короче, никогда длиннее: d(v) <= dist[v]. Поэтому оценка по ходу работы падает, а не растёт, и в момент, когда падать некуда, она и есть ответ.

Три постановки задачи (первую в литературе сокращают до SSSP, single-source shortest paths - «кратчайшие пути из одного источника»; сокращение запоминать не обязательно, но в поиске оно помогает):

из одной вершины во все         - Дейкстра, Беллман-Форд, порядок по ДАГу
из одной вершины в одну         - те же алгоритмы, можно остановиться на цели
                                  (либо A* из главы про эвристики)
между всеми парами              - Флойд-Уоршелл, Джонсон

Массив prev даёт сам маршрут, а не только его длину: от цели идём по prev назад до старта и переворачиваем. Это общая деталь всех алгоритмов раздела - хранить не только числа, но и «откуда пришли».

Свойство оптимальной подструктуры. Любой кусок кратчайшего пути сам является кратчайшим путём между своими концами. Иначе его можно было бы заменить на более дешёвый и улучшить весь путь - а он кратчайший, значит улучшить нельзя. На этом свойстве стоит вообще всё: именно оно позволяет строить кратчайшие пути «по кусочкам», релаксируя рёбра по одному.

Правило

Вес ребра - число на нём, длина пути - сумма весов. dist[v] - оценка СВЕРХУ кратчайшего расстояния; все алгоритмы раздела улучшают её РЕЛАКСАЦИЕЙ: dist[v] = min(dist[v], dist[u] + w(u, v)), попутно запоминая prev[v] = u для восстановления маршрута. Отличаются алгоритмы только порядком релаксаций. Любой подпуть кратчайшего пути сам кратчайший (оптимальная подструктура) - именно поэтому путь можно собирать по кусочкам. Обход в ширину решает задачу лишь при РАВНЫХ весах: он считает число рёбер, а не сумму.

Разбор: почему обход в ширину ошибается

Граф со схемы неориентированный, ребра проходятся в любую сторону: s - t весом 10, s - m весом 1, m - t весом 1. В релаксациях сторона названа стрелкой, потому что релаксируют ребро ВСЕГДА в конкретную сторону: s → t - это «улучшить оценку t, придя из s».

Обход в ширину из s кладёт в очередь соседей: t (по ребру весом 10) и m. Он размечает t сразу - «уровень 1» - и больше к нему не возвращается, потому что вершина уже посещена. Ответ обхода: до t один шаг. Как число РЁБЕР это правда, но как расстояние - нет: путь s → m → t стоит 1 + 1 = 2, а прямое ребро - 10.

Почему так вышло: обход в ширину помечает вершину при ПЕРВОМ попадании и считает вопрос закрытым. В невзвешенном графе это законно - первое попадание и есть кратчайшее, ведь все рёбра равны. Во взвешенном первое попадание ничего не гарантирует: дешёвый путь может прийти позже, потому что он длиннее в рёбрах.

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

Разбор: релаксация по шагам

Тот же граф, посмотрим на массив оценок. В начале: dist[s] = 0, dist[m] = dist[t] = +∞.

1. Релаксируем s → t (вес 10): dist[s] + 10 = 10 < +∞ → dist[t] = 10, prev[t] = s.
2. Релаксируем s → m (вес 1): 0 + 1 = 1 < +∞ → dist[m] = 1, prev[m] = s.
3. Релаксируем m → t (вес 1): dist[m] + 1 = 2 < 10 → dist[t] = 2, prev[t] = m.

Оценка dist[t] менялась: сначала 10, потом 2. Это нормально - dist всегда остаётся оценкой СВЕРХУ и только уменьшается. Маршрут читается по prev с конца: t ← m ← s, то есть s → m → t.

Обрати внимание на важное: КОНЕЧНЫЙ результат не зависит от того, в каком порядке мы релаксировали рёбра, - он зависит только от того, все ли нужные релаксации выполнены. А вот сколько релаксаций понадобится, порядок решает: относись к нему как к порядку сборки. Пройди рёбра «по течению» - и каждого хватит по разу; пройди против - и к тем же рёбрам придётся вернуться, потому что в первый раз ты релаксировал из вершины, оценка которой была ещё завышена. Именно поэтому существуют разные алгоритмы с разным порядком: Дейкстра выбирает порядок умно и обходится одним проходом по каждому ребру, Беллман-Форд не выбирает вовсе и просто повторяет релаксации V − 1 раз. Оба правы, цена разная.

Что ломается без этого

Первое: применять обход в ширину ко взвешенному графу - самая частая ошибка, и она молчит: ответ выглядит правдоподобным. Второе: считать dist окончательным значением, а не оценкой сверху, - и удивляться, что оно меняется по ходу. Третье: забыть prev и получить только длину пути, когда нужен сам маршрут; восстановить его потом уже нельзя, надо считать заново. Четвёртое: веса-нули и отрицательные веса - они ломают разные алгоритмы по-разному, и об этом будут отдельные уроки; пока запомни, что вопрос «какие бывают веса» надо задавать ДО выбора алгоритма. Пятое: путать «кратчайший путь» и «путь с наименьшим числом рёбер» - это разные задачи, и вторая решается обходом в ширину независимо от весов.

Зачем это в работе

Кратчайшие пути - это навигаторы и логистика (длина, время, пробки, цена топлива), маршрутизация пакетов в сетях (метрика канала), планирование перемещений в играх и робототехнике, расчёт «стоимости» в любых графах состояний - от подбора последовательности действий до поиска дешёвого преобразования строки. Релаксация как приём выходит далеко за пределы этой главы: она же лежит в основе динамического программирования на графах, а идея «держать оценку сверху и улучшать её» встречается в алгоритмах потоков и в методах оптимизации. А понимание, что обход в ширину - частный случай Дейкстры при равных весах, экономит время: если веса одинаковы, не надо тащить кучу, обычной очереди достаточно и она в разы быстрее.

Теперь сам

Граф: s→a весом 4, s→b весом 1, b→a весом 2, a→t весом 1, b→t весом 7. Проведи релаксации в порядке записи рёбер и выпиши dist и prev после каждой. Каким получится маршрут до t?