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

Введение

Использование алгоритма Флойда – Уоршелла позволяет определить самые короткие пути между любой парой вершин графа. Согласно условию задачи, имеем неориентированный или ориентированный взвешенный граф G, который имеет n вершин. Необходимо определить величину всех кратчайших путей d(i, j) между вершинами i и j, при условии отсутствия в графе циклов с отрицательными весами (в этом случае решения для некоторых пар вершин могут быть бесконечно малыми, то есть несуществующими). Данный алгоритм описали в своих работах независимо друг от друга и примерно в одно и тоже время Роберт Флойд и Стивен Уоршелл в 1962-м году. В их честь и назвали алгоритм, именуемый и сегодня алгоритмом Флойда – Уоршелла. Однако следует заметить, что ещё в 1959-ом году Бернардом Роем был разработан почти аналогичный алогитм, но он не был тогда никем замечен.

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

Главный идейный постулат алгоритма заключается в разделении процедуры нахождения самых коротких путей на отдельные фазы. В начале к-той фазы (где к = 1…n) предполагается, что есть матрица расстояний d [ ] , в которой хранятся величины самых коротких путей, содержащих как внутренние, только вершины из набора { 1, 2,…, k – 1}. Все вершины графа пронумерованы с цифры один. То есть, в начале к-той фазы значение d[i][j], равняется величине самого короткого пути между вершинами i и j, при условии, что этот путь содержит только вершины, имеющие номера меньше К (начальная и конечная точка маршрута при этом не учитываются). Достаточно просто проверить, что для выполнения этого условия в первой фазе, надо в матрицу дистанций d[ ] [ ] вписать матрицу смежности графа: d[i][j]=g[i][j] — цена ребра между вершинами i и j. В случае, если есть вершины, не соединённые рёбрами, то необходимо вписать бесконечное значение. Расстояние из вершины i в вершину i (то есть в саму себя) необходимо всегда принимать за нуль, это важно для работы алгоритма.

Предположим, что алгоритм находится в к-той фазе, и необходимо сделать перерасчёт матрицы d[ ] [ ] для её соответствия условиям для к+1-ой фазы. Произведём фиксацию некоторых вершин i и j. Получается пара абсолютно различных вариантов:

1. Самый короткий маршрут из вершины i к вершине j, который имеет разрешение добавочно пройти через вершины { 1,2,…,k}, совпал с самым коротким маршрутом, с разрешением прохождения через вершины набора { 1,2,…,k – 1}. Это означает, что значение d[i][j] останется прежним при смене фазы с к-той на к+1-ую фазу.
2. Вновь созданный самый короткий маршрут становится лучше, чем прежний маршрут.

Значит новый самый короткий маршрут должен проходить через вершину К. Следует заметить, что при этом не теряется общность, если рассматривать дальше лишь простые маршруты (то есть такие маршруты, которые не проходят два раза через какую-либо вершину). Но тогда надо так же отметить, что в случае разбиения этого нового маршрута некоей вершиной k на два участка (один идёт от i к вершине к, а другой от «k» к вершине j), то каждый из участков уже не посещает вершину к. Выходит, что размер каждого из этих участков был определён ещё на К-1-ой фазе или даже ранее, и можно просто определить суммарную величину d[i] [k] + d[k] [j], которая будет размером нового самого короткого маршрута. Если объединить эти два варианта, то получим, что при к-той фазе необходимо рассчитать размеры самых коротких путей среди всех пар вершин i и j по следующей формуле: nеw_d[i][j] = min (d[i][j], d[i][k] + d[k][j]).

То есть выходит, что весь объём работ, подлежащих выполнению в К-той фазе, заключается в переборе всех пар вершин и пересчёте размеров самых коротких путей среди них. В итоге по завершению функционирования n-ой фазы, в матрице дистанций d[i][j] окажется размер самого короткого маршрута от i до j, или бесконечность, в случае отсутствия маршрута между вершинами. И напоследок надо отметить, что возможно и не формировать новую матрицу nеw_d[ ][ ] в качестве хранилища самых коротких маршрутов на к-той фазе. Всё можно менять и хранить сразу в матрице d[ ][ ]. Поскольку, в случае улучшения (уменьшения) какого-либо числа в матрице дистанций, не происходит ухудшения размера самого короткого маршрута для каких-либо иных пар вершин, которые обрабатывались позже. Чтобы вычислить асимптотику этого алгоритма, необходимо воспользоваться формулой: $O(n^3)$

Программное выполнение алгоритма

Входными данными программы является граф, который задаётся как матрица смежности, то есть двумерный массив d[ ][ ] с размером n*n, где любой компонент означает размер ребра между какими-либо вершинами. Необходимо выполнение условия d[i] [j] = 0 при всех i.

Рисунок 1. Код. Автор24 — интернет-биржа студенческих работ

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

Рисунок 2. Код. Автор24 — интернет-биржа студенческих работ

Восстановление маршрутов

Возможно простыми средствами сохранять добавочные информационные данные (о прошедших событиях), которые позволят восстановить самый короткий маршрут между любой парой определённых вершин в форме последовательного прохождения вершин. Чтобы это работало, хватит, кроме матрицы дистанций d[ ] [ ] сохранять так называемую матрицу «предков»p[ ] [ ] , в которой для всех пар вершин содержится нумерация фаз, при которых найдено самое короткое расстояние между вершинами.