Алгоритм Флойда

Алгоритм Флойда (алгоритм Флойда–Уоршелла) — алгоритм нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а в случае, когда такой цикл есть, позволяет найти хотя бы один такой цикл. Алгоритм работает за [math] \Theta(n^3) [/math] времени и использует [math] \Theta(n^2) [/math] памяти. Разработан в 1962 году.

Алгоритм

Постановка задачи

Текущий (синий) путь и потенциально более короткий (красный)

Дан взвешенный ориентированный граф [math] G(V, E) [/math]; [math]\omega_{uv} = \begin{cases} \text{weight of }uv ,& \text{if } uv \in E \\ +\infty ,& \text{if } uv \notin E \end{cases}[/math], в котором вершины пронумерованы от [math]1[/math] до [math]n[/math]. Требуется найти матрицу кратчайших расстояний [math] d [/math], в которой элемент [math] d_{ij} [/math] либо равен длине кратчайшего пути из [math] i [/math] в [math] j [/math], либо равен [math] +\infty [/math], если вершина [math] j [/math] не достижима из [math] i [/math].

Описание

Обозначим длину кратчайшего пути между вершинами [math] u [/math] и [math] v [/math], содержащего, помимо [math]u[/math] и [math]v[/math], только вершины из множества [math] \{ 1 .. i \} [/math] как [math]d_{uv}^{(i)}[/math], [math]d_{uv}^{(0)} = \omega_{uv}[/math].

На каждом шаге алгоритма, мы будем брать очередную вершину (пусть её номер — [math] i [/math]) и для всех пар вершин [math]u[/math] и [math]v[/math] вычислять [math] d_{uv}^{(i)} = \min(d_{uv}^{(i-1)}, d_{ui}^{(i-1)} + d_{iv}^{(i-1)}) [/math]. То есть, если кратчайший путь из [math]u[/math] в [math]v[/math], содержащий только вершины из множества [math] \{ 1 .. i \} [/math], проходит через вершину [math]i[/math], то кратчайшим путем из [math] u [/math] в [math] v [/math] является кратчайший путь из [math] u [/math] в [math] i [/math], объединенный с кратчайшим путем из [math] i [/math] в [math] v [/math]. В противном случае, когда этот путь не содержит вершины [math] i [/math], кратчайший путь из [math]u[/math] в [math]v[/math], содержащий только вершины из множества [math] \{ 1 .. i \} [/math] является кратчайшим путем из [math]u[/math] в [math]v[/math], содержащим только вершины из множества [math] \{ 1 .. i-1 \} [/math].

Код (в первом приближении)

[math]d^{(0)}_{uv} = w[/math]
for i = 1 to n
    for u = 1 to n
        for v = 1 to n
            [math] d^{(i)}_{uv} = \min(d^{(i - 1)}_{uv}, d^{(i - 1)}_{ui} + d^{(i - 1)}_{iv}) [/math]

В итоге получаем, что матрица [math] d^{(n)} [/math] и является искомой матрицей кратчайших путей, поскольку содержит в себе длины кратчайших путей между всеми парами вершин, имеющих в качестве промежуточных вершин вершины из множества [math] \{ 1..n \} [/math], что есть попросту все вершины графа. Такая реализация работает за [math] \Theta(n^3) [/math] времени и использует [math] \Theta(n^3) [/math] памяти.

Код (окончательный)

Утверждается, что можно избавиться от одной размерности в массиве [math] d [/math], т.е. использовать двумерный массив [math]d_{uv}[/math]. В процессе работы алгоритма поддерживается инвариант [math]\rho(u, v) \leqslant d_{uv} \leqslant d_{uv}^{(i)}[/math], а, поскольку, после выполнения работы алгоритма [math] \rho(u, v) = d_{uv}^{(i)} [/math], то тогда будет выполняться и [math] \rho(u, v) = d_{uv} [/math].

Утверждение:

В течение работы алгоритма Флойда выполняются неравенства: [math]\rho(u, v) \leqslant d_{uv} \leqslant d_{uv}^{(i)}[/math].

[math]\triangleright[/math]

После инициализации все неравенства, очевидно, выполняются. Далее, массив [math] d [/math] может измениться только в строчке 5. Докажем второе неравенство индукцией по итерациям алгоритма. Пусть также [math]d'_{uv}[/math] — значение [math]d_{uv}[/math] сразу после [math]i - 1[/math] итерации. Покажем, что [math] d_{uv} \leqslant d_{uv}^{(i)} [/math], зная, что [math] d'_{uv} \leqslant d_{uv}^{(i - 1)} [/math]. Рассмотрим два случая: Значение [math] d_{uv}^{(i)} [/math] стало меньше, чем [math] d_{uv}^{(i - 1)} [/math]. Тогда [math] d_{uv}^{(i)} = d_{ui}^{(i-1)} + d_{iv}^{(i-1)} \geqslant [/math] (выполняется на шаге [math] i - 1 [/math], по индукционному предположению) [math] \geqslant d'_{ui} + d'_{iv} \ge[/math] (в силу выполнения 7-ой строчки алгоритма на [math]i[/math]-ой итерации и невозрастания элементов массива [math] d [/math]) [math]\geqslant d_{uv}[/math]. В ином случае всё очевидно: [math] d_{uv}^{(i)} = d_{uv}^{(i - 1)} \geqslant d'_{uv} \geqslant d_{uv} [/math], и неравенство тривиально. Докажем первое неравенство от противного. Пусть неравенство было нарушено, рассмотрим момент, когда оно было нарушено впервые. Пусть это была [math]i[/math]-ая итерация и в этот момент изменилось значение [math]d_{uv}[/math] и выполнилось [math]\rho(u,v) \gt d_{uv}[/math]. Так как [math]d_{uv}[/math] изменилось, то [math]d_{uv} = d_{ui} + d_{iv} \ge[/math] (так как ранее [math]\forall u, v \in V: \rho(u,v) \leqslant d_{uv}[/math]) [math]\geqslant \rho(u, i) + \rho(i, v) \ge[/math] (по неравенству треугольника) [math]\geqslant \rho(u, v)[/math]. Итак [math]d_{uv} \geqslant \rho(u,v)[/math] — противоречие.

[math]\triangleleft[/math]

func floyd(w):
    d = w
    for i = 1 to n
        for u = 1 to n
            for v = 1 to n
                d[u][v] = min(d[u][v], d[u][i] + d[i][v])

Данная реализация работает за время [math] \Theta(n^3) [/math], но требует уже [math] \Theta(n^2) [/math] памяти. В целом, алгоритм Флойда очень прост, и, поскольку в нем используются только простые операции, константа, скрытая в определении [math] \Theta [/math] весьма мала.

Пример работы

[math]i = 0[/math]	[math]i = 1[/math]	[math]i = 2[/math]	[math]i = 3 [/math]	[math]i = 4[/math]
[math]\begin{pmatrix} \times & 1 & 6 & \infty \\ \infty & \times & 4 & 1 \\ \infty & \infty & \times & \infty \\ \infty & \infty & 1 & \times \\ \end{pmatrix}[/math]	[math]\begin{pmatrix} \times & 1 & 6 & \infty \\ \infty & \times & 4 & 1 \\ \infty & \infty & \times & \infty \\ \infty & \infty & 1 & \times \\ \end{pmatrix}[/math]	[math]\begin{pmatrix} \times & 1 & \bf{5} & \bf{2} \\ \infty & \times & 4 & 1 \\ \infty & \infty & \times & \infty \\ \infty & \infty & 1 & \times \\ \end{pmatrix}[/math]	[math]\begin{pmatrix} \times & 1 & 5 & 2 \\ \infty & \times & 4 & 1 \\ \infty & \infty & \times & \infty \\ \infty & \infty & 1 & \times \\ \end{pmatrix}[/math]	[math]\begin{pmatrix} \times & 1 & \bf{3} & 2 \\ \infty & \times & \bf{2} & 1 \\ \infty & \infty & \times & \infty \\ \infty & \infty & 1 & \times \\ \end{pmatrix}[/math]

Вывод кратчайшего пути

Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив [math]next[/math], в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из [math]u[/math] в [math]v[/math] по кратчайшему пути.

Модифицированный алгоритм

func floyd(w):
    d = w
    for i = 1 to n
        for u = 1 to n
            for v = 1 to n
                if d[u][i] + d[i][v] < d[u][v]
                    d[u][v] = d[u][i] + d[i][v]
                    next[u][v] = i

func get_shortest_path(u, v):
    if d[u][v] == [math]\infty[/math]
        print "No path found"                 // между вершинами u и v нет пути
    c = u
    while c != v
        print c
        c = next[c][v]
    print v

Нахождение отрицательного цикла

Утверждение:

При наличии цикла отрицательного веса в матрице [math] D [/math] появятся отрицательные числа на главной диагонали.

[math]\triangleright[/math]

Так как алгоритм Флойда последовательно релаксирует расстояния между всеми парами вершин [math](i, j)[/math], в том числе и теми, у которых [math]i = j[/math], а начальное расстояние между парой вершин [math](i, i)[/math] равно нулю, то релаксация может произойти только при наличии вершины [math] k [/math] такой, что [math] d[i][k] + d[k][i] \lt 0 [/math], что эквивалентно наличию отрицательного цикла, проходящего через вершину [math] i [/math].

[math]\triangleleft[/math]

Из доказательства следует, что для поиска цикла отрицательного веса необходимо, после завершения работы алгоритма, найти вершину [math] i [/math], для которой [math] d[i][i] \lt 0 [/math], и вывести кратчайший путь между парой вершин [math] (i, i) [/math]. При этом стоит учитывать, что при наличии отрицательного цикла расстояния могут уменьшаться экспоненциально. Для предотвращения переполнения все вычисления стоит ограничивать снизу величиной [math]-INF[/math], либо проверять наличие отрицательных чисел на главной диагонали во время подсчета.

Литература

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд — М.: Издательский дом «Вильямс», 2009. — ISBN 978-5-8459-0857-5.
• Википедия - Алгоритм Флойда — Уоршелла
• Wikipedia - Floyd–Warshall algorithm