39. Метод Уоршалла и Флойда нахождения кратчайшего расстояния между всеми парами вершин графа. Временная сложность алгоритма. Сравнение с методом Дейкстры

 

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

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

 

Ремарка

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

 

Алгоритм

 

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

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

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

Псевдокод


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



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

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

 

Сравнение с алгоритмом Дейкстры

Поскольку версия алгоритма Дейкстры с использованием матрицы смежности находит кратчайшие пути от одной вершины за время порядка О(л), то в этом случае применение алгоритма Дейкстры для нахождения всех кратчайших путей потребует времени порядка О(л), т.е. получим такой же временной порядок, как и в алгоритме Флойда. Константы пропорциональности в порядках времени выполнения для обоих алгоритмов зависят от применяемых компилятора и вычислительной машины, а также от особенностей реализации алгоритмов. Вычислительный эксперимент и измерение времени выполнения - самый простой путь подобрать лучший алгоритм для конкретного приложения.