Рассмотрим общую задачу поиска кратчайших путей между всеми парами узлов в помеченном ориентированном графе . Для любой упорядоченной пары узлов требуется найти путь из в наименьшей стоимости.
Первый способ заключается в применении алгоритма Дейкстры, выбирая поочередно каждый узел орграфа в качестве источника. Пусть n=|V|. Временная сложность алгоритма Дейкстры O(n2). Применяя его в цикле для каждого из n узлов, получим временную сложность алгоритма O(n3).
Второй способ заключается в применении алгоритма, известного как алгоритм Флойда-Варшалла (Floyd-Warshall algorithm) или алгоритма Флойда. Временная сложность его в худшем случае также равна O(n3).
Как и ранее, наличие в орграфе дуг с отрицательным весом допускается, но предполагается, что контуры с отрицательным весом отсутствуют.
В алгоритме Флойда рассматриваются "промежуточные" узлы кратчайшего пути. Промежуточным узлом простого пути называется произвольный узел, отличный от и т.е. это любой узел из множества .
Предположим, что орграф состоит из узлов . Рассмотрим подмножество узлов для некоторого . Для произвольной пары узлов рассмотрим все пути из узла в узел , все промежуточные узлы которых выбраны из множества . Пусть среди этих путей — путь с минимальным весом (этот путь простой). В алгоритме Флойда используется взаимосвязь между путем р и кратчайшими путями из узла в узел , все промежуточные узлы которых принадлежат множеству . Эта взаимосвязь зависит от того, является ли узел k промежуточным на пути .
Если — не промежуточный узел пути , то все промежуточные узлы этого пути принадлежат множеству . Таким образом, кратчайший путь из узла в узел со всеми промежуточными узлами из множества одновременно является кратчайшим путем из узла в узел со всеми промежуточными узлами из множества .
Рис.4.2.1.
Если — промежуточный узел пути , то этот путь, как видно из рис. 4.2.1, можно разбить следующим образом: . Поскольку не является промежуточным узлом пути , понятно, что —кратчайший путь из узла в узел , все промежуточные узлы которого принадлежит множеству . Аналогично, — кратчайший путь из узла в узел , все промежуточные узлы которого принадлежат множеству .
Алгоритм Флойда использует матрицу размера , в которой элемент содержит длину кратчайшего пути из узла в узел , найденного к данной итерации. Используется также матрица , в которой элемент содержит последний узел, добавленный к пути из узла в узел к моменту текущей итерации.
Далее нижний индекс обозначает значение матрицы или P после -й итерации
Начальные значения на 0-й итерации: – вес дуги для всех . Таким образом, на начальном этапе кратчайшим путем из узла в узел считается непосредственно дуга , если она существует. На этом пути нет промежуточных узлов, поэтому . Если дуга отсутствует, то
Кратчайший путь из узла в узел имеет, очевидно, стоимость 0, и не имеет промежуточных узлов, поэтому , .
Над матрицей выполняется итераций.
После -й итерации содержит наименьшую длину путей из узла в узел , которые могут проходить через узлы из множества и не проходят через узлы из множества .
На-й итерации для вычисления матрицы применяется следующая формула:
Графическая интерпретация этой формулы показана на рис 4.2.2.
Рис. 4.2.2 Включение узла в путь от узла к узлу
Это означает, что для вычисления проводится сравнение величины (т.е. стоимость пути от узла к узлу без участия узла или другого узла с более высоким номером) с величиной (стоимость пути от узла до узла плюс стоимость пути от узла до узла ).
Если путь через узел дешевле, чем ,то величина заменяется на . При этом в матрице P фиксируется добавление к кратчайшему пути из узла в узел промежуточного узла : .
В противном случае стоимость кратчайшего пути не меняется: и узел к пути не добавляется: . В частности, это всегда будет происходить при и при , так как в этих случаях уже входит в путь и его включение, как промежуточного узла, не сократит стоимость. Таким образом, на -й итерации не меняются элементы -й строки и -го столбца матриц A и P.
Заметим, что поскольку кратчайший путь из узла в узел имеет, стоимость 0, и не имеет промежуточных узлов, то начальные значения диагональных элементов , не будут меняться в процессе итераций.
Пример.
Рис. 4.2.3 Помеченный ориентированный граф
На рис. 4.2.3 показан помеченный орграф, а далее представлены значения матриц А и P после трех итераций.
A0
P0
A1
P1
∞
∞
∞
A2
P2
A3
P3
Равенства и означают, что на -й итерации элементы матрицы , стоящие в -й строке и -м столбце, не изменяются.
Приведем примеры вычисления матриц A и P на различных итерациях алгоритма. Цветом выделены ячейки, значения которых подлежат пересчету на данной итерации.
По окончательным значениям матриц A3 и P3 восстановим кратчайшие пути и их стоимости.
От узла 1 до узла 2: , . Кратчайший путь , его стоимость .
От узла 1 до узла 3: . Кратчайший путь , его стоимость .
От узла 2 до узла 1: . Кратчайший путь , его стоимость .
От узла 2 до узла 3: , . Кратчайший путь , его стоимость .
От узла 3 до узла 1: , . Кратчайший путь , его стоимость .
