Алгоритм Флойда — Уоршелла

Алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования. Это базовый алгоритм, так что тем кто его знает — можно дальше не читать.

Этот алгоритм был одновременно опубликован в статьях Роберта Флойда (Robert Floyd) и Стивена Уоршелла (Stephen Warshall) в 1962 г., хотя в 1959 г. Бернард Рой (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.

Ремарка

Если граф не содержит рёбер с отрицательным весом, то для решения этой проблемы можно использовать алгоритм Дейкстры для нахождения кратчайшего пути от одной вершины до всех остальных, запустив его на каждой вершине. Время работы такого алгоритма зависит от типа данных, который мы будем использовать для алгоритма Дейкстры, это может быть как простая очередь с приоритетом, так и бинарная или фибоначчиева Куча, соответственно время работы будет варьироваться от O(V³) до O(V*E*log(V)), где V количество вершин, а E — рёбер. («О»-большое).

Если же есть рёбера с отрицательным весом, можно использовать алгоритм Беллмана — Форда. Но этот алгоритм, запущенный на всех вершинах графа, медленнее, время его работы O(V²*E), а в сильно «густых» графах аж O(V⁴).

Динамическое программирование

Что значит динамический алгоритм? Динамическое программирование — это альтернатива решению задач методом «в лоб», то есть brute forc'ом или жадными алгоритмами. Используется там, где оптимальное решение подзадачи меньшего размера может быть использовано для решения исходной задачи. В общем виде метод выглядит так:

1. Разбиение задачи на подзадачи меньшего размера.
2. Нахождение оптимального решения подзадач рекурсивно.
3. Использование полученного решения подзадач для конструирования решения исходной задачи.

Для нахождения кратчайших путей между всеми вершинами графа используется не перебор всех возможностей, что приведет к большому времени работы и потребует больше памяти, а восходящее динамическое программирование, то есть все подзадачи, которые впоследствии понадобятся для решения исходной задачи, просчитываются заранее и затем используются.

Структура кратчайшего пути

В основе алгоритма лежат два свойства кратчайшего пути графа. Первое:

Имеется кратчайший путь p_1k=(v₁,v₂,… ,v_k) от вершины v₁ до вершины v_k, а также его подпуть p'(v_i,v_i+1,… ,v_j), при этом действует 1 <= i <= j <= k.

Если p — кратчайший путь от v₁ до v_k, то p' также является кратчайшим путем от вершины v_i до v_j

Это можно легко доказать, так как стоимость пути p складывается из стоимости пути p' и стоимости остальных его частей. Так вот представив что есть более короткий путь p', мы уменьшим эту сумму, что приведет к противоречию с утверждением, что эта сумма и так уже была минимальной.

Второе свойство является основой алгоритма. Мы рассматриваем граф G с пронумерованными от 1 до n вершинами {v₁,v₂,… ,v_n} и путь p_ij от v_i до v_j, проходящий через определенное множество разрешенных вершин, ограниченное индексом k.

То есть если k=0, то мы рассматриваем прямые соединения вершин друг с другом, так как множество разрешенных промежуточных вершин рано нулю. Если k=1 — мы рассматриваем пути, проходящие через вершину v₁, при k=2 — через вершины {v₁, v₂}, при k=3 — {v₁, v₃, v₃} и так далее.

Например у нас есть такой граф (слева) и k=1, то есть в качестве промужуточных узлов разрешен только узел «1». В этом графе при k=1 нет пути p₄₃, но есть при k=2, тогда можно добраться из «4» в «3» через «2» или через «1» и «2».

Рассмотрим кратчайший путь p_ij с разрешенными промужуточными вершинами {1..k-1} стоимостью d_ij. Теперь расширим множество на k- тый элемент, так что множество разрешенных вершин станет {1..k}. При таком расширении возможно 2 исхода:

Случай 1. Элемент k не входит в кратчайший путь p_ij, то есть от добавления дополнительной вершины мы ничего не выиграли и ничего не изменили, а значит стоимость кратчайшего пути d^k_ij не изменился, соответственно

d^k_ij = d^k-1_ij — просто перенимаем значение до увеличения k.

Случай 2. Элемент k входит в кратчайший путь p_ij, то есть после добавления новой вершины в можество разрешенных, кратчайший путь изменился и проходит теперь через вершину v_k. Какую стоимость получит новый путь?

Новый кратчайший путь разбит вершиной v_k на p_ik и p_kj, используем первое свойство, согласно ему, p_ik и p_kj также кратчайшие пути от v_i до v_k и от v_k до v_j соответственно. Значит

d^k_ij = d^k_ik + d^k_kj

А так как в этих путях k либо конечный, либо начальный узел, то он не входит в множество промежуточных, соответственно его из него можно удалить:

d^k_ij = d^k-1_ik + d^k-1_kj

Алгоритм

Посмотрим на значение d^k_ij в обоих случаях — верно! оно в обоих случаях складывается из значений d для k-1, а значит имея начальные (k=0) значения для d, мы сможем расчитать d для всех последующих значений k. А значения d для k=0 мы знаем, это вес/стоимость рёбер графа, то есть соединений без промужуточных узлов.

При k=n (n — количество вершин) мы получим оптимальные значения d для всех пар вершин.

При увеличении с k-1 до k, какое значение мы сохраним для d^k_ik? Минимумом значений случая 1 и 2, то есть смотрим дешевле ли старый путь или путь с добавлением дополнительной вершины.

Псевдокод

Наконец сам алгоритм. Мы используем представление графа в виде матрицы cмежностей.



Как видно алгоритм очень прост — сначала происходит инициализация матрицы кратчайших расстояний D⁰, изначально она совпадает с матрицей смежности, в цикле увеличиваем значение k и пересчитываем матрицу расстояний, из D⁰ получаем D¹, из D¹ — D² и так далее до k=n.

Предполагается, что если между двумя какими-то вершинами нет ребра, то в матрице смежности было записано какое-то большое число (достаточно большое, чтобы оно было больше длины любого пути в этом графе); тогда это ребро всегда будет невыгодно брать, и алгоритм сработает правильно. Правда, если не принять специальных мер, то при наличии в графе рёбер отрицательного веса, в результирующей матрице могут появиться числа вида ∞-1, ∞-2, и т.д., которые, конечно, по-прежнему означают, что между соответствующими вершинами вообще нет пути. Поэтому при наличии в графе отрицательных рёбер алгоритм Флойда лучше написать так, чтобы он не выполнял переходы из тех состояний, в которых уже стоит «нет пути»

Пример

Первый пересчет матрицы — изменяется одно значение, из-за расширения множества разрешенных вершин на вершину «1» мы смогли добраться от вершины «4» до «2», используя более дешевый путь.

d^k_ij = min( d^k-1_ij; d^k-1_ik + d^k-1_kj )

d¹₄₂ = min( d⁰₄₂, d⁰₄₁ + d⁰₁₂)

d¹₄₂ = min( 4, -1)

Вторая итерация, улучшили значение для p₄₃



Результат



Тут и там можно поиграть с аплетом и посмотреть как в живую работает алгоритм.

Анализ времени работы и использования памяти

Алгоритму требуется O(n³) памяти, для сохранения матриц. Однако количество матриц можно легко сократить до двух, каждый раз переписывая ненужную матрицу или вообще перейти к двухмерной матрице, убрав индекс k у d^k_ij. Лучший вариант, который чаще всего используется — писать сразу в матрицу смежности, тогда нам совсем не нужна дополнительная память, правда если сразу переписывать изначальную матрицу, то нужно дополнительно показать корректность алгоритма, так как классическое академическоле доказательство верно только для случая, когда матрица предыдущей итерации не изменяется.

Что касается времени работы — три вложенных цикла от 1 до n — Θ(n³).

Случай отрицательных циклов

Если в графе есть циклы отрицательного веса, то формально алгоритм Флойда-Уоршелла к такому графу неприменим. Но на самом деле алгоритм корректно сработает для всех пар, пути мужду которыми никогда не проходят через цикл негативной стоимости, а для остальных мы получим какие-нибудь числа, возможно сильно отрицательные. Алгоритм можно научить выводить для таких пар некое значение, соответствующее -∞

Кстати после отработки такого графа на диагонале матрицы кратчайших путей возникнут отрицательные числа — кратчайшее расстояние от вершины в этом цикле до неё самой будет меньше нуля, что соответствует проходу по этому циклу, так что алгоритм можно использовать для определения наличия отрицательных циклов в графе.

Реконструирование пути

Матрица расстояний покажет нам кратчайшее (самое дешевое) растояние для любой пары вершин, а как же узнать путь? Очень просто, при расчете d^k_ij нужно расчитать еще и π^k_ij. π^k_ij при этом — предшественник вершины v_j на пути от v_i с множеством разрешенных промежуточных вершин {1..k}.

Я просто оставлю это сдесь, остально додумать может каждый сам

Применение

Как и любой базовый алгоритм, алгоритм Флойда — Уоршелла используется очень широко и много где, начиная от поиска транзитивного замыкания графа, заканчивая генетикой и управлением проектами. Но первое что приходит в голову конечно же транспортные и всякие другие сети.

Скажем если вы возьмете карту города — её транспортная система это граф, соответственно присвоив каждому ребру некую стоимость, расчитанную скажем из пропускной способности и других важный параметров — вы сможете подвести попутчика по самому короткому/быстрому/дешевому пути.





<sub>На этом всё, написано не очень, так что если укажите на ошибки, несостыковки, непонятки и прочее, буду благодарен, текст мне этот еще нужен будет :)

Спасибо Rustam'у и mastersobg'у за поправки</sub>