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

Алгоритм Флойда (алгоритм Флойда–Уоршелла) — динамический алгоритм нахождения длин кратчайших путей между всеми парами вершин взвешенного ориентированного графа. Разработан в 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]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]i[/math], затем из [math]i[/math] в [math]v[/math], иначе ничего менять не будем.

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

 # Инициализация
 d[0] = w
 # Основная часть
 for i in {1..n}:
   for u in {1..n}:
     for v in {1..n}:
       d[i][u][v] = min(d[i-1][u][v], d[i-1][u][i] + d[i-1][i][v])

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

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

 # Инициализация
 d = w
 # Основная часть
 for i in {1..n}:
   for u in {1..n}:
     for v in {1..n}:
       d[u][v] = min(d[u][v], d[u][i] + d[i][v])

Алгоритм всегда завершит работу за [math]O(V^3)[/math] — как несложно видеть, три вложенных цикла выполняются по [math]n[/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]t_{uv}[/math], в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из [math]u[/math] в [math]v[/math] по кратчайшему пути.

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

 # Инициализация
 d = w
 t[u][v] = v если есть ребро uv
 # Основная часть
 for i in {1..n}:
   for u in {1..n}:
     for v in {1..n}:
       if (d[u][i] + d[i][v]) < d[u][v]: 
         d[u][v] = d[u][i] + d[i][v]
         t[u][v] = t[u][i]

 # Вывод кратчайшего пути
 def get_shortest_path(u, v):
   if d[u][v] == inf:
       raise NoPath # Из u в v пути нет
   c = u
   while c != v:
     yield c
     c = t[c][v]
   yield v

Литература

• Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)