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

Понятия

Вес ребра - число на нём; длина пути - сумма весов; dist[v] - текущая оценка сверху на расстояние от старта; prev[v] - предыдущая вершина в найденном пути (по ней путь разворачивается назад).

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

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

Алгоритмы кратчайших путей отличаются только ПОРЯДКОМ релаксаций (остовы раздела строятся иначе - по свойству разреза). dist[v] всё время остаётся длиной какого-то реального пути, поэтому оценка не бывает меньше правды.

Оптимальность подпути - любой участок кратчайшего пути сам кратчайший; из неё следует, что дерево путей prev существует и что релаксации хватает.

Отрицательный цикл, достижимый из старта и ведущий к цели, - кратчайшего пути нет вовсе: длину можно уменьшать бесконечно. Отсюда две разные постановки - «кратчайший путь» и «простой путь наименьшего веса» (вторая NP-трудна).

Эвристика h(v) - дешёвая оценка остатка до цели. Допустимая: h(v) <= d(v, цель). Согласованная: h(u) <= w(u, v) + h(v) и h(цель) = 0.

Остовное дерево - связный подграф без циклов на всех V вершинах, ровно V − 1 ребро; минимальное (МОД) - наименьшего суммарного веса. Разрез - разбиение вершин на две непустые части.

Что унести

Выбор алгоритма кратчайших путей - это выбор по весам, а не по вкусу:

Неотрицательность весов нужна Дейкстре ровно в одном месте доказательства - «остаток пути >= 0, значит извлечённая вершина окончательна». С минусом это место рушится, и вершину приходится открывать заново.

Три приёма, которые сводят задачу к уже решённой:

A*        =  Дейкстра при w'(u,v) = w(u,v) + h(v) − h(u)   (согласованность ⇔ w' ≥ 0)
Джонсон   =  Дейкстра при w'(u,v) = w(u,v) + p(u) − p(v)   (потенциалы p - от Беллмана-Форда)
длиннейший путь в DAG  =  кратчайший при отрицанных весах

Оба перевеса меняют длину любого пути u → v на одну и ту же величину, поэтому порядок путей сохраняется, а отрицательные веса исчезают.

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

Минимальные остовные деревья - одна теорема и три способа её применить:

Свойство разреза доказывается обменом: добавили лёгкое ребро - появился ровно один цикл, в нём есть другое ребро через тот же разрез, выбросили его, вес не вырос. Свойство цикла - обратная сторона: самое тяжёлое ребро цикла можно не брать. При различных весах МОД единственно.

Главная путаница раздела - в одном слагаемом. best[u] = wt[j] строит остов, а best[u] = best[v] + wt[j] - дерево кратчайших путей. Код почти одинаковый, деревья разные.

Тихие ошибки, которые собирал этот раздел: остановиться, когда цель попала в очередь, а не когда извлечена; «исправить» Дейкстру под минусы прибавлением константы (она умножает добавку на число рёбер и меняет ответ); релаксировать в Беллмане-Форде без флага «изменилось ли» и терять раннюю остановку; забыть h(цель) = 0; взять «расстояние по прямой» там, где вес - цена, а не длина; ждать МОД от несвязного графа (там остовный лес).

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

Дальше - потоки, паросочетания и линейное программирование. К весам добавятся пропускные способности, а жадный шаг научится ОТКАТЫВАТЬСЯ: обратное ребро остаточной сети - это разрешение передумать, которого не было ни у Дейкстры, ни у Крускала.