Содержание

1 Алгоритм Флойда

Алгоритм Флойда

Постановка

Алгоритм Флойда(-Уоршелла) ищет попарные кратчайшие пути в графе $G = (V, E)$ без отрицательных циклов. В случае наличия в графе отрицательных циклов, алгоритм может вернуть один из них.

Решение с помощью динамического программирования

Пусть все вершины в графе пронумерованы от $1$ до $n$, а вес ребра между вершинами $i$ и $j$ равен $w(i, j)$.

Определение

Введём динамическое программирование $sp[i][j][k]$ --- длина кратчайшего пути в графе между вершинами $i$, и $j$, при условии, что все промежуточные вершины имеют номера, не превосходящие $k$. Обратите внимание, что на $i$ и $j$ это ограничение не распространяется.

База

$ \begin{equation} sp[i][j][0]=\begin{cases} w(i, j), & \text{если $(i, j) \in E$}.\\ 0, & \text{иначе}. \end{cases} \end{equation} $

Пересчёт

На $k$-м уровне динамического программирования, мы разрешаем путям между вершинами посещать вершину с номером $k$. От этого пути между какими-то $i$ и $j$ могли сократиться за счёт прохода по пути $i ~- k$, а затем по $k ~- j$.

Таким образом, формула пересчёта устроена следующим образом ($k \geq 1$): $ \begin{equation} sp[i][j][k]=min\begin{cases} sp[i][j][k - 1]\\ sp[i][k][k - 1] + sp[k][j][k - 1] \end{cases} \end{equation} $

Where is the money the answer, Lebowsky?

Кратчайшее расстояние между вершинами $i$ и $j$ находится в $sp[i][j][n]$.

Восстановление ответа

Если нам нужно дополнительно восстанавливать ответ, то надо по ходу алгоритма для каждой пары $i$ и $j$ запоминать вторую вершину на кратчайшем пути.

Уменьшаем затраты памяти

Обратим внимание на то, что в динамическом программировании нам в каждый момент требуется хранить только предыдущий $k-1$-й слой, поэтому можно сократить затраты памяти в $n$ раз, убрав последнее измерение.

Если же вовсе убрать последнее измерение из всех формул, то теперь на $k$-м шаге динамическое программирование для какой-то пары вершин может учитывать уже обновлённое значение, и тем самым посчитать значение с $k+1$-го или больше уровня динамики. Но если нам важно лишь получить кратчайшие расстояния в конце, то этот спецэффект не является проблемой и после $n$ шагов мы всё равно получим кратчайшие расстояния, просто, возможно, они посчитаются пораньше.

А что с отрицательными циклами?

Теорема

В графе есть отрицательный цикл $\iff$ после $n$ внешних итераций алгоритма на главной диагонали стоит отрицательное число. Более того, все вершины $i$, для которых $sp[i][i] < 0$ лежат на каком-то цикле отрицательного веса.

Доказательство

$\impliedby$

Если на главной диагонали в какой-то момент оказалось отрицательное число, значит в какой-то момент было верно, что $sp[i][k] + sp[k][j] < 0$, что в точности означает, что цикл $ i ~- k ~- i$ имеет отрицательный вес.

$\implies$

Пусть в графе есть отрицательный цикл $C$. Возьмём какую-нибудь вершину $i$ из него. Пусть $k$ --- наибольший номер среди вершин из $C$ кроме $i$. Если таких нет, то $C$ --- петля отрицательного веса и на главной диагонали изначально стоит отрицательное число.

Заметим, что на $k$-й итерации алгоритма для $sp[i][i]$ будет в том числе рассматриваться значение $sp[i][k] + sp[k][i]$. Причём $sp[i][k] \leq |C[i:k]| \land sp[k][i] \leq |C[k:i]| \implies sp[i][k] + sp[k][i] \leq |C| < 0 \implies $ на $k$-й итерации в $sp[i][i]$ будет стоять отрицательное число, а значит после всех итераций и подавно. $C[i:k]$ --- часть цикла $C$ между вершинами $i$ и $k$ при каком-то фиксированном обходе. $C[k:i]$ --- оставшаяся часть цикла.

Вывод отрицательного цикла

Алгоритм очень простой

Найти $i$ такую что $sp[i][i] < 0$
Запустить алгоритм восстановления кратчайшего пути из $i$ в $i$.

Заметим, что мы выводим лишь какой-то цикл отрицательного веса. В худшем случае их может быть порядка $n!$. Упражнение: в каком графе?

Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex