Алгоритм Флойда Уоршалла
Мы хотим определить кратчайшие пути между всеми парами вершин. Мы могли бы использовать Дейкстра из Беллман Форд, с каждой вершиной в качестве источника. Можем ли мы сделать лучше? В алгоритме Флойда Уоршалла мы предполагаем, что у нас есть доступ к график с n вершинами в виде матрицы смежности n².
Алгоритм Флойда Уоршалла принимает в качестве входных данных ориентированный и оцененный граф, описанный матрицей смежности, дающей вес дуги, когда она существует, и значение ∞ в противном случае. Вес пути между двумя вершинами равен сумме весов дуг, составляющих этот путь. Дуги графа могут иметь отрицательные веса, но граф не должен иметь цепи строго отрицательного веса. Алгоритм вычисляет для каждой пары вершин минимальный вес среди всех путей между этими двумя вершинами.
Условия.
- Расширенный общий случай
Мы предполагаем, что вершинами G являются {1, 2, 3, 4,..., нет}. Он последовательно решает следующие подзадачи:
Вткij — минимальный вес пути из вершины i в вершину я используя только промежуточные вершины в {1, 2, 3, …, к}, если он есть, и ∞ в противном случае. Отметим Wк матрица Wкиж.
При k = 0 Вт0 — матрица смежности, определяющая граф.
Чтобы найти рекуррентное соотношение, рассмотрим путь п Между я и я минимального веса, промежуточные вершины которого лежат в {1, 2, 3,..., к} :
- то есть п не бери верх к
- то есть п заимствовать ровно один раз вершину к и п Таким образом, это соединение двух путей между я и к и к и я соответственно, чьи промежуточные вершины лежат в {1, 2, 3,..., к-1}.
Пусть p — кратчайший путь из i в j со всеми промежуточными вершинами множества {1,. . . , к}. Если k не является промежуточной вершиной p, то p также является кратчайшей со всеми промежуточными вершинами множества {1,. . . , к – 1}. Если k является промежуточной вершиной p, мы разлагаем p на путь p1 между i и k и путь p2 между k и j; это самые короткие пути.
Приведенное выше наблюдение дает рекуррентное соотношение:
Вткij=мин(Втк-1ij, Втк-1ик +Wк-1К Дж ), для каждого я, я и к в {1, 2, 3, 4…, нет}.
Таким образом, мы решаем подзадачи, увеличивая значение k.
Что дает первые два шага:
Пример алгоритма Флойда Уоршалла
Первая матрица — это матрица соседних, а затем кратчайших путей. Вторая матрица представляет предшественников. Он инициализируется значением z, равным номеру строки, если значение существует в матрице смежности (в начальном состоянии). Матрица-предшественник обновляется каждый раз, когда изменяется значение в (i, j). Соответствующее значение в (i, j) матрицы предшественников равно количеству итераций (то есть значению мощности матрицы).
Оптимальность алгоритма Флойда Уоршалла
Изначально у нас есть кратчайшие пути размера 1, начинающиеся из всех вершин. Затем мы вычисляем пути большего размера, проходящие через вершину 1, и оставляем только самые короткие пути. Таким образом, новая итерация отображает кратчайшие пути размера 1 и пути размера 2, проходящие через вершину 1. По индукции мы выводим, что последняя матрица отображает кратчайшие пути размера меньше, чем количество вершин между любой парой вершин.
CODE W - матрица смежности
за к от 1 до п
за я от 1 до н
за j от 1 до n Wкij=мин(Втк-1ij, Втк-1ик +Wк-1К Дж )
конец
конец
конец
вернуть W
RU 
FR 
EN 
ES