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

МГПИ им. М.Е. Евсевьева

 

 

 

 

 

 

Доклад по ТОИ  на тему:

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

 

 

 

 

Выполнил: студент группы МДИ-110 Рябов Евгений

Проверила: Пауткина Ольга Ивановна

 

 

 

 

 

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

Алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования. Это базовый алгоритм, так что тем кто его знает — можно дальше не читать. 
 
Этот алгоритм был одновременно опубликован в статьях Роберта Флойда (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, то есть смотрим дешевле ли старый путь или путь с добавлением дополнительной вершины. 
 

Пример

 
 
 
Первый пересчет матрицы — изменяется одно значение, из-за расширения множества  разрешенных вершин на вершину «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³).

Применение

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

Саранск 2013