Дейкстра, A*, Форд-Беллман, поиск отрицательного цикла, Джонсон, Флойд-Уоршелл. Формулировки — по лекциям курса. Для каждого: определение → идея → корректность → асимптотика → что спросят.
Поддерживаем множество S вершин, для которых расстояние уже вычислено корректно. Изначально S={s}, d[s]=0, остальные ∞. Повторяем: среди вершин вне S берём вершину v с минимальной оценкой d[v], добавляем в S (теперь d[v]=dist(s,v) окончательно), релаксируем рёбра (v,t): d[t]=min(d[t], d[v]+w(v,t)).
Доказываем индукцией, что в момент добавления v в S верно d[v]=dist(s,v). Пусть нет: тогда есть более короткий путь, который выходит из S в вершину t вне S раньше v. Но d[t] ≥ d[v] (иначе выбрали бы t), а хвост пути от t до v имеет неотрицательный вес, поэтому dist(s,v) ≥ d[t] ≥ d[v] — противоречие. Именно неотрицательность весов делает алгоритм верным.
| Контейнер | Релаксация | Извлечение min | Итого |
|---|---|---|---|
| Массив | O(1) | O(|V|) | O(|V|²) |
| Приоритетная очередь | O(log|V|) | O(log|V|) | O(|E| log|V|) |
| Фибоначчиева куча | O*(1) | O(log|V|) | O(|E|+|V| log|V|) |
То же, что Дейкстра, но вершины сравниваются не по g(v) (оценка dist(s,v)), а по f(v) = g(v) + h(v), где h(v) — эвристика, оценка расстояния от v до цели t. Если h≡0 — вырождается в Дейкстру.
Любая монотонная эвристика допустима (доказывается индукцией по рёберной длине кратчайшего пути от u до t). Пример монотонной эвристики — евклидово расстояние до цели на карте дорог: неравенство на разницу эвристик следует из неравенства треугольника.
dp[v][k] = минимальный вес пути из ≤ k рёбер из s в v.
База: dp[s][0]=0, остальные ∞.
Переход: dp[v][k] = min(dp[v][k], min по (u,v) dp[u][k−1] + w(u,v)).
Ответ: dist(s,v) = dp[v][|V|−1]. Достаточно хранить один слой → память O(|V|).
Простой кратчайший путь содержит не более |V|−1 рёбер (иначе в нём повторилась бы вершина = цикл, а без отрицательных циклов цикл не улучшает путь). За k итераций мы находим кратчайшие пути из ≤ k рёбер, поэтому |V|−1 итераций достаточно.
Время O(|V|·|E|), память O(|V|).
Запускаем Форд-Беллман на |V| итераций. Если на |V|-й итерации произошла релаксация (расстояние до достижимой из s вершины уменьшилось по сравнению с (|V|−1)-й) — значит есть отрицательный цикл, достижимый из s.
Простой кратчайший путь ≤ |V|−1 рёбер, поэтому после |V|−1 итераций он стабилизируется. Релаксация на |V|-й итерации означает, что нашёлся непростой путь дешевле любого простого — а это возможно только при отрицательном цикле. Обратно: цикл длины ≤ |V|, поэтому на |V|-й итерации хотя бы одна его вершина обновится.
Храним предка par[v], из которого вершина релаксировалась. От вершины, обновившейся на |V|-й итерации, пройдём |V| предков (гарантированно попадём внутрь цикла), затем по par соберём сам цикл.
Все пары кратчайших путей в разреженном графе с отрицательными рёбрами — быстрее, чем Флойд O(|V|³).
Ключевое свойство: для любого пути s→t вес меняется на одну и ту же величину φ(s)−φ(t) (телескопическая сумма). Значит множество кратчайших путей не меняется при переходе к w_φ.
Существование неотрицательного потенциала ⇔ нет отрицательных циклов. Конструкция: добавить фиктивную вершину s₀ с рёбрами веса 0 ко всем; φ(v) = dist(s₀, v). Тогда w_φ(u,v) = dist(s₀,u) + w(u,v) − dist(s₀,v) ≥ 0 (по неравенству для кратчайших путей).
Время O(|V||E| + |V|·Дейкстра) = O(|V||E| log|V|) с кучей — обычно быстрее Флойда.
dp[u][v][k] = минимальный вес пути из u в v, у которого все промежуточные вершины имеют номера < k.
База: dp[u][u][0]=0, остальные ∞ (или вес ребра).
Переход: dp[u][v][k] = min(dp[u][v][k−1], dp[u][k][k−1] + dp[k][v][k−1]) — либо не используем вершину k, либо проходим через неё.
Слой k зависит только от k−1 → память сжимается до O(|V|²) (можно даже один слой in-place).
Время O(|V|³), память O(|V|²).
Если после работы dp[i][i] < 0 для какой-то вершины i — через i проходит отрицательный цикл.