Алгоритм Флойда — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 30: Строка 30:
  
 
=== Код (окончательный) ===
 
=== Код (окончательный) ===
Утверждается, что можно избавиться от одной размерности в массиве <tex> d </tex>, т.е. использовать двумерный массив <tex>d_{uv}</tex>. В процессе работы алгоритма поддерживается инвариант <tex>\rho(u, v) \le d_{uv} \le d_{uv}^i</tex>, а значит <tex>d_{uv}</tex> тоже в итоге сойдутся к решению.
+
Утверждается, что можно избавиться от одной размерности в массиве <tex> d </tex>, т.е. использовать двумерный массив <tex>d_{uv}</tex>. В процессе работы алгоритма поддерживается инвариант <tex>\rho(u, v) \le d_{uv} \le d_{uv}^{(i)}</tex>, а, поскольку, после выполнения работы алгоритма <tex> \rho(u, v) == d_{uv}^{(i)} </tex>, то тогда будет выполняться и <tex> \rho(u, v) == d_{uv} </tex>.
 +
 
 +
{{Утверждение
 +
|statement=
 +
В течение работы алгоритма Флойда выполняются неравенства: <tex>\rho(u, v) \le d_{uv} \le d_{uv}^{(i)}</tex>.
 +
|proof=
 +
 
 +
После инициализации все неравенства, очевидно, выполняются. Далее, массив <tex> d </tex> может измениться только в строчке 5. Докажем оба неравенства по индукции по итерациям алгоритма:
 +
 
 +
# <tex> \rho(u, v) \le d_{uv} </tex>. Рассмотрим два случая:
 +
#* Значение <tex> d_{uv} </tex> изменилось. Тогда <tex> d_{uv} = d_{ui} + d_{iv} \ge \rho(u, i) + \rho(i, v) \ge \rho(u, v) </tex> (по индукционному предположению и неравенству треугольника для <tex> \rho </tex>).
 +
#* Значение <tex> d_{uv} </tex> не изменилось. Тогда неравенство выполняется автоматически по индукционному предположению.
 +
# <tex> d_{uv} \le d_{uv}^{(i)} </tex>. Аналогично рассмотрим два случая:
 +
#* Значение <tex> d_{uv}^{(i)} </tex> изменилось. Тогда <tex> d_{uv}^{(i)} \ge d_{ui}^{(i-1)} + d_{iv}^{(i-1)} \ge d_{ui}^{(i)} + d_{iv}^{(i)} \ge d_{ui} + d_{uv} \ge d_{uv} </tex>, по индукционному предположению и тому факту, что <tex> d_{uv}^{(i)} </tex> невозрастает с ростом <tex> i </tex>.
 +
#* В ином случае всё очевидно: <tex> d_{uv}^{(i)} = d_{uv}^{(i - 1)} \ge d_{uv} </tex>, и неравенство тривиально.
 +
 
 +
}}
  
 
   # Инициализация
 
   # Инициализация
   d = w
+
   <tex dpi = "105"> d = w </tex>
 
   # Основная часть
 
   # Основная часть
 
   for i in {1..n}:
 
   for i in {1..n}:
 
     for u in {1..n}:
 
     for u in {1..n}:
 
       for v in {1..n}:
 
       for v in {1..n}:
         d[u][v] = min(d[u][v], d[u][i] + d[i][v])
+
         <tex dpi = "105"> d_{uv} = min(d_{uv}, d_{ui} + d_{iv}) </tex>
  
Алгоритм всегда завершит работу за <tex>O(V^3)</tex> — как несложно видеть, три вложенных цикла выполняются по <tex>n</tex> раз каждый.
+
Данная реализация работает за время <tex> \Theta(n^3) </tex>, но требует уже <tex> \Theta(n^2) </tex> памяти. В целом, алгоритм Флойда очень прост, и, поскольку в нем используются только простые операции, константа, скрытая в определении <tex> \Theta </tex> весьма мала.
  
 
=== Пример работы ===
 
=== Пример работы ===
Строка 81: Строка 97:
  
 
== Вывод кратчайшего пути ==
 
== Вывод кратчайшего пути ==
Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив <tex>t_{uv}</tex>, в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из <tex>u</tex> в <tex>v</tex> по кратчайшему пути.
+
Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив <tex>next_{uv}</tex>, в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из <tex>u</tex> в <tex>v</tex> по кратчайшему пути.
  
 
=== Модифицированный алгоритм ===
 
=== Модифицированный алгоритм ===
Строка 94: Строка 110:
 
         if (d[u][i] + d[i][v]) < d[u][v]:  
 
         if (d[u][i] + d[i][v]) < d[u][v]:  
 
           d[u][v] = d[u][i] + d[i][v]
 
           d[u][v] = d[u][i] + d[i][v]
           t[u][v] = t[u][i]
+
           next[u][v] = next[u][i]
  
 
   # Вывод кратчайшего пути
 
   # Вывод кратчайшего пути
Строка 102: Строка 118:
 
     c = u
 
     c = u
 
     while c != v:
 
     while c != v:
       yield c
+
       print c
       c = t[c][v]
+
       c = next[c][v]
     yield v
+
     print v
  
 
[[Файл:Floyd_path.png]]
 
[[Файл:Floyd_path.png]]

Версия 04:30, 1 ноября 2011

Алгоритм Флойда (алгоритм Флойда–Уоршелла) — алгоритм нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а в случае, когда такой цикл есть, позволяет найти хотя бы один такой цикл. Этот алгоритм работает в течение времени [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)} = w [/math]
 # Основная часть
 for i in {1..n}:
   for u in {1..n}:
     for v in {1..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) \le d_{uv} \le d_{uv}^{(i)}[/math], а, поскольку, после выполнения работы алгоритма [math] \rho(u, v) == d_{uv}^{(i)} [/math], то тогда будет выполняться и [math] \rho(u, v) == d_{uv} [/math].

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

После инициализации все неравенства, очевидно, выполняются. Далее, массив [math] d [/math] может измениться только в строчке 5. Докажем оба неравенства по индукции по итерациям алгоритма:

  1. [math] \rho(u, v) \le d_{uv} [/math]. Рассмотрим два случая:
    • Значение [math] d_{uv} [/math] изменилось. Тогда [math] d_{uv} = d_{ui} + d_{iv} \ge \rho(u, i) + \rho(i, v) \ge \rho(u, v) [/math] (по индукционному предположению и неравенству треугольника для [math] \rho [/math]).
    • Значение [math] d_{uv} [/math] не изменилось. Тогда неравенство выполняется автоматически по индукционному предположению.
  2. [math] d_{uv} \le d_{uv}^{(i)} [/math]. Аналогично рассмотрим два случая:
    • Значение [math] d_{uv}^{(i)} [/math] изменилось. Тогда [math] d_{uv}^{(i)} \ge d_{ui}^{(i-1)} + d_{iv}^{(i-1)} \ge d_{ui}^{(i)} + d_{iv}^{(i)} \ge d_{ui} + d_{uv} \ge d_{uv} [/math], по индукционному предположению и тому факту, что [math] d_{uv}^{(i)} [/math] невозрастает с ростом [math] i [/math].
    • В ином случае всё очевидно: [math] d_{uv}^{(i)} = d_{uv}^{(i - 1)} \ge d_{uv} [/math], и неравенство тривиально.
[math]\triangleleft[/math]
 # Инициализация
 [math] d = w [/math] 
 # Основная часть
 for i in {1..n}:
   for u in {1..n}:
     for v in {1..n}:
       [math] d_{uv} = min(d_{uv}, d_{ui} + d_{iv}) [/math]

Данная реализация работает за время [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]
Floyd step0.png Floyd step1.png Floyd step2.png Floyd step3.png Floyd step4.png
[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_{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]
         next[u][v] = next[u][i]
 # Вывод кратчайшего пути
 def get_shortest_path(u, v):
   if d[u][v] == inf:
       raise NoPath # Из u в v пути нет
   c = u
   while c != v:
     print c
     c = next[c][v]
   print v

Floyd path.png

Литература

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