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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Нахождение отрицательного цикла)
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 4 участников)
Строка 4: Строка 4:
  
 
=== Постановка задачи ===
 
=== Постановка задачи ===
[[Файл:Floyd_1.png|right|thumb|180px|Текущий (синий) путь и потенциально более короткий (красный)]]
+
[[Файл:Floyd_first.png|right|thumb|180px|Текущий (синий) путь и потенциально более короткий (красный)]]
  
Дан взвешенный ориентированный граф <tex> G(V, E) </tex>; <tex>\omega_{uv} =
+
Дан взвешенный ориентированный [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|граф]] <tex> G(V, E) </tex>, в котором вершины пронумерованы от <tex>1</tex> до <tex>n</tex>.
 +
 
 +
<tex>\omega_{uv} =
 
\begin{cases}
 
\begin{cases}
 
\text{weight of }uv ,& \text{if } uv \in E \\
 
\text{weight of }uv ,& \text{if } uv \in E \\
 
+\infty ,& \text{if } uv \notin E
 
+\infty ,& \text{if } uv \notin E
\end{cases}</tex>, в котором вершины пронумерованы от <tex>1</tex> до <tex>n</tex>. Требуется найти матрицу кратчайших расстояний <tex> d </tex>, в которой элемент <tex> d_{ij} </tex> либо равен длине кратчайшего пути из <tex> i </tex> в <tex> j </tex>, либо равен <tex> +\infty </tex>, если вершина <tex> j </tex> не достижима из <tex> i </tex>.
+
\end{cases}</tex><br>Требуется найти матрицу кратчайших расстояний <tex> d </tex>, в которой элемент <tex> d_{ij} </tex> либо равен длине кратчайшего пути из <tex> i </tex> в <tex> j </tex>, либо равен <tex> +\infty </tex>, если вершина <tex> j </tex> не достижима из <tex> i </tex>.
  
 
=== Описание ===
 
=== Описание ===
Строка 16: Строка 18:
 
Обозначим длину кратчайшего пути между вершинами <tex> u </tex> и <tex> v </tex>, содержащего, помимо <tex>u</tex> и <tex>v</tex>, только вершины из множества <tex> \{ 1 .. i \} </tex> как <tex>d_{uv}^{(i)}</tex>, <tex>d_{uv}^{(0)} = \omega_{uv}</tex>.
 
Обозначим длину кратчайшего пути между вершинами <tex> u </tex> и <tex> v </tex>, содержащего, помимо <tex>u</tex> и <tex>v</tex>, только вершины из множества <tex> \{ 1 .. i \} </tex> как <tex>d_{uv}^{(i)}</tex>, <tex>d_{uv}^{(0)} = \omega_{uv}</tex>.
  
На каждом шаге алгоритма, мы будем брать очередную вершину (пусть её номер {{---}} <tex> i </tex>) и для всех пар вершин <tex>u</tex> и <tex>v</tex> вычислять <tex> d_{uv}^{(i)} = min(d_{uv}^{(i-1)}, d_{ui}^{(i-1)} + d_{iv}^{(i-1)}) </tex>. То есть, если кратчайший путь из <tex>u</tex> в <tex>v</tex>, содержащий только вершины из множества <tex> \{ 1 .. i \} </tex>, проходит через вершину <tex>i</tex>, то кратчайшим путем из <tex> u </tex> в <tex> v </tex> является кратчайший путь из <tex> u </tex> в <tex> i </tex>, объединенный с кратчайшим путем из <tex> i </tex> в <tex> v </tex>. В противном случае, когда этот путь не содержит вершины <tex> i </tex>, кратчайший путь из <tex>u</tex> в <tex>v</tex>, содержащий только вершины из множества <tex> \{ 1 .. i \} </tex> является кратчайшим путем из <tex>u</tex> в <tex>v</tex>, содержащим только вершины из множества <tex> \{ 1 .. i-1 \} </tex>.
+
На каждом шаге алгоритма, мы будем брать очередную вершину (пусть её номер {{---}} <tex> i </tex>) и для всех пар вершин <tex>u</tex> и <tex>v</tex> вычислять <tex> d_{uv}^{(i)} = \min(d_{uv}^{(i-1)}, d_{ui}^{(i-1)} + d_{iv}^{(i-1)}) </tex>. То есть, если кратчайший путь из <tex>u</tex> в <tex>v</tex>, содержащий только вершины из множества <tex> \{ 1 .. i \} </tex>, проходит через вершину <tex>i</tex>, то кратчайшим путем из <tex> u </tex> в <tex> v </tex> является кратчайший путь из <tex> u </tex> в <tex> i </tex>, объединенный с кратчайшим путем из <tex> i </tex> в <tex> v </tex>. В противном случае, когда этот путь не содержит вершины <tex> i </tex>, кратчайший путь из <tex>u</tex> в <tex>v</tex>, содержащий только вершины из множества <tex> \{ 1 .. i \} </tex> является кратчайшим путем из <tex>u</tex> в <tex>v</tex>, содержащим только вершины из множества <tex> \{ 1 .. i-1 \} </tex>.
  
 
=== Код (в первом приближении) ===
 
=== Код (в первом приближении) ===
  # Инициализация
+
<tex>d^{(0)}_{uv} = w</tex>
  <tex dpi = "105"> d^{(0)} = w </tex>
+
'''for''' <tex>i \in V</tex>
  # Основная часть
+
    '''for''' <tex>u \in V</tex>
  for i in {1..n}:
+
        '''for''' <tex>v \in V</tex>
    for u in {1..n}:
+
            <tex> d^{(i)}_{uv} = \min(d^{(i - 1)}_{uv}, d^{(i - 1)}_{ui} + d^{(i - 1)}_{iv}) </tex>
      for v in {1..n}:
 
        <tex dpi = "105" > d^{(i)}_{uv} = min(d^{(i - 1)}_{uv}, d^{(i - 1)}_{ui} + d^{(i - 1)}_{iv}) </tex>
 
  
 
В итоге получаем, что матрица <tex> d^{(n)} </tex> и является искомой матрицей кратчайших путей, поскольку содержит в себе длины кратчайших путей между всеми парами вершин, имеющих в качестве промежуточных вершин вершины из множества <tex> \{ 1..n \} </tex>, что есть попросту все вершины графа. Такая реализация работает за <tex> \Theta(n^3) </tex> времени и использует <tex> \Theta(n^3) </tex> памяти.
 
В итоге получаем, что матрица <tex> d^{(n)} </tex> и является искомой матрицей кратчайших путей, поскольку содержит в себе длины кратчайших путей между всеми парами вершин, имеющих в качестве промежуточных вершин вершины из множества <tex> \{ 1..n \} </tex>, что есть попросту все вершины графа. Такая реализация работает за <tex> \Theta(n^3) </tex> времени и использует <tex> \Theta(n^3) </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>.
+
Утверждается, что можно избавиться от одной размерности в массиве <tex> d </tex>, т.е. использовать двумерный массив <tex>d_{uv}</tex>. В процессе работы алгоритма поддерживается инвариант <tex>\rho(u, v) \leqslant d_{uv} \leqslant d_{uv}^{(i)}</tex>, а, поскольку, после выполнения работы алгоритма <tex> \rho(u, v) = d_{uv}^{(i)} </tex>, то тогда будет выполняться и <tex> \rho(u, v) = d_{uv} </tex>.
  
 
{{Утверждение
 
{{Утверждение
 
|statement=
 
|statement=
В течение работы алгоритма Флойда выполняются неравенства: <tex>\rho(u, v) \le d_{uv} \le d_{uv}^{(i)}</tex>.
+
В течение работы алгоритма Флойда выполняются неравенства: <tex>\rho(u, v) \leqslant d_{uv} \leqslant d_{uv}^{(i)}</tex>.
 
|proof=
 
|proof=
  
Строка 43: Строка 43:
 
Пусть также <tex>d'_{uv}</tex> {{---}} значение <tex>d_{uv}</tex> сразу после <tex>i - 1</tex> итерации.
 
Пусть также <tex>d'_{uv}</tex> {{---}} значение <tex>d_{uv}</tex> сразу после <tex>i - 1</tex> итерации.
  
Покажем, что <tex> d_{uv} \le d_{uv}^{(i)} </tex>, зная, что <tex> d'_{uv} \le d_{uv}^{(i - 1)} </tex>.
+
Покажем, что <tex> d_{uv} \leqslant d_{uv}^{(i)} </tex>, зная, что <tex> d'_{uv} \leqslant d_{uv}^{(i - 1)} </tex>.
  
 
Рассмотрим два случая:
 
Рассмотрим два случая:
* Значение <tex> d_{uv}^{(i)} </tex> стало меньше, чем <tex> d_{uv}^{(i - 1)} </tex>. Тогда <tex> d_{uv}^{(i)} = d_{ui}^{(i-1)} + d_{iv}^{(i-1)} \ge </tex> (выполняется на шаге <tex> i - 1 </tex>, по индукционному  предположению) <tex> \ge d'_{ui}  + d'_{iv} \ge</tex> (в силу выполнения 7-ой строчки алгоритма на <tex>i</tex>-ой итерации и невозрастания элементов массива <tex> d </tex>) <tex>\ge d_{uv}</tex>.
+
* Значение <tex> d_{uv}^{(i)} </tex> стало меньше, чем <tex> d_{uv}^{(i - 1)} </tex>. Тогда <tex> d_{uv}^{(i)} = d_{ui}^{(i-1)} + d_{iv}^{(i-1)} \geqslant </tex> (выполняется на шаге <tex> i - 1 </tex>, по индукционному  предположению) <tex> \geqslant d'_{ui}  + d'_{iv} \ge</tex> (в силу выполнения 7-ой строчки алгоритма на <tex>i</tex>-ой итерации и невозрастания элементов массива <tex> d </tex>) <tex>\geqslant d_{uv}</tex>.
* В ином случае всё очевидно: <tex> d_{uv}^{(i)} = d_{uv}^{(i - 1)} \ge d'_{uv} \ge d_{uv} </tex>, и неравенство тривиально.
+
* В ином случае всё очевидно: <tex> d_{uv}^{(i)} = d_{uv}^{(i - 1)} \geqslant d'_{uv} \geqslant d_{uv} </tex>, и неравенство тривиально.
  
  
 
'''Докажем первое неравенство от противного.'''
 
'''Докажем первое неравенство от противного.'''
  
Пусть неравенство было нарушено, рассмотрим момент, когда оно было нарушено впервые. Пусть это была <tex>i</tex>-ая итерация и в этот момент изменилось значение <tex>d_{uv}</tex> и выполнилось  <tex>\rho(u,v) > d_{uv}</tex>. Так как <tex>d_{uv}</tex> изменилось, то <tex>d_{uv} = d_{ui} + d_{iv} \ge</tex> (так как ранее <tex>\forall u, v \in V: \rho(u,v) \le d_{uv}</tex>) <tex>\ge \rho(u, i) + \rho(i, v) \ge</tex> (по неравенству треугольника) <tex>\ge \rho(u, v)</tex>.  
+
Пусть неравенство было нарушено, рассмотрим момент, когда оно было нарушено впервые. Пусть это была <tex>i</tex>-ая итерация и в этот момент изменилось значение <tex>d_{uv}</tex> и выполнилось  <tex>\rho(u,v) > d_{uv}</tex>. Так как <tex>d_{uv}</tex> изменилось, то <tex>d_{uv} = d_{ui} + d_{iv} \ge</tex> (так как ранее <tex>\forall u, v \in V: \rho(u,v) \leqslant d_{uv}</tex>) <tex>\geqslant \rho(u, i) + \rho(i, v) \ge</tex> (по неравенству треугольника) <tex>\geqslant \rho(u, v)</tex>.  
Итак <tex>d_{uv} \ge \rho(u,v)</tex> {{---}} противоречие.
+
Итак <tex>d_{uv} \geqslant \rho(u,v)</tex> {{---}} противоречие.
 
}}
 
}}
  
  # Инициализация
+
'''func''' floyd(w)''':'''
  <tex dpi = "105"> d = w </tex>  
+
    d = <tex>\omega</tex>                <font color="green">// изначально <tex>d = \omega</tex></font>
  # Основная часть
+
    '''for''' <tex>i \in V</tex>
  for i in {1..n}:
+
        '''for''' <tex>u \in V</tex>
    for u in {1..n}:
+
            '''for''' <tex>v \in V</tex>
      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> \Theta(n^3) </tex>, но требует уже <tex> \Theta(n^2) </tex> памяти. В целом, алгоритм Флойда очень прост, и, поскольку в нем используются только простые операции, константа, скрытая в определении <tex> \Theta </tex> весьма мала.
 
Данная реализация работает за время <tex> \Theta(n^3) </tex>, но требует уже <tex> \Theta(n^2) </tex> памяти. В целом, алгоритм Флойда очень прост, и, поскольку в нем используются только простые операции, константа, скрытая в определении <tex> \Theta </tex> весьма мала.
Строка 70: Строка 69:
 
| <tex>i = 0</tex> ||  <tex>i = 1</tex> ||  <tex>i = 2</tex> ||  <tex>i = 3 </tex> || <tex>i = 4</tex>
 
| <tex>i = 0</tex> ||  <tex>i = 1</tex> ||  <tex>i = 2</tex> ||  <tex>i = 3 </tex> || <tex>i = 4</tex>
 
|-
 
|-
|width = "180px"| [[Файл:Floyd_2_0.png|170px]] ||width = "180px"|[[Файл:Floyd_2_1.png|170px]] ||width = "180px"|[[Файл:Floyd_2_2.png|170px]] ||width = "180px"|[[Файл:Floyd_2_3.png|170px]] ||width = "180px"|[[Файл:Floyd_2_4.png|170px]]
+
|width = "180px"| [[Файл:0.png|170px]] ||width = "180px"|[[Файл:Floyd_1.png|170px]] ||width = "180px"|[[Файл:Floyd_2.png|170px]] ||width = "180px"|[[Файл:Floyd_algo_3.png|170px]] ||width = "180px"|[[Файл:Floyd_4.png|170px]]
 
|-
 
|-
 
| <tex>\begin{pmatrix}
 
| <tex>\begin{pmatrix}
Строка 105: Строка 104:
  
 
== Вывод кратчайшего пути ==
 
== Вывод кратчайшего пути ==
Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив <tex>next_{uv}</tex>, в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из <tex>u</tex> в <tex>v</tex> по кратчайшему пути.
+
Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив <tex>next</tex>, в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из <tex>u</tex> в <tex>v</tex> по кратчайшему пути.
  
 
=== Модифицированный алгоритм ===
 
=== Модифицированный алгоритм ===
 
+
'''func''' floyd(w)''':'''
  # Инициализация
+
    d = <tex>\omega</tex>              <font color="green">// изначально <tex>d = \omega</tex></font>
  d = w
+
    '''for''' <tex>i \in V</tex>
  t[u][v] = v если есть ребро uv
+
        '''for''' <tex>u \in V</tex>
  # Основная часть
+
            '''for''' <tex>v \in V</tex>
  for i in {1..n}:
+
                '''if''' d[u][i] + d[i][v] < d[u][v]
    for u in {1..n}:
+
                    d[u][v] = d[u][i] + d[i][v]
      for v in {1..n}:
+
                    next[u][v] = next[u][i]
        if (d[u][i] + d[i][v]) < d[u][v]:
 
          d[u][v] = d[u][i] + d[i][v]
 
          next[u][v] = i
 
  
  # Вывод кратчайшего пути
+
'''func''' getShortestPath(u, v)''':'''
  def get_shortest_path(u, v):
+
    '''if''' d[u][v] == <tex>\infty</tex>
    if d[u][v] == inf:
+
        '''print''' "No path found"                <font color="green">// между вершинами u и v нет пути</font>
        raise NoPath # Из u в v пути нет
+
    c = u
    c = u
+
    '''while''' c != v
    while c != v:
+
        '''print''' c
      print c
+
        c = next[c][v]
      c = next[c][v]
+
    '''print''' v
    print v
 
  
 
== Нахождение отрицательного цикла ==
 
== Нахождение отрицательного цикла ==
Строка 137: Строка 132:
 
Так как алгоритм Флойда последовательно релаксирует расстояния между всеми парами вершин <tex>(i, j)</tex>, в том числе и теми, у которых <tex>i = j</tex>, а начальное расстояние между парой вершин <tex>(i, i)</tex> равно нулю, то релаксация может произойти только при наличии вершины <tex> k </tex> такой, что <tex> d[i][k] + d[k][i] < 0 </tex>, что эквивалентно наличию отрицательного цикла, проходящего через вершину <tex> i </tex>.
 
Так как алгоритм Флойда последовательно релаксирует расстояния между всеми парами вершин <tex>(i, j)</tex>, в том числе и теми, у которых <tex>i = j</tex>, а начальное расстояние между парой вершин <tex>(i, i)</tex> равно нулю, то релаксация может произойти только при наличии вершины <tex> k </tex> такой, что <tex> d[i][k] + d[k][i] < 0 </tex>, что эквивалентно наличию отрицательного цикла, проходящего через вершину <tex> i </tex>.
 
}}
 
}}
Из доказательства следует, что для поиска цикла отрицательного веса необходимо, после завершения работы алгоритма, найти вершину <tex> i </tex>, для которой <tex> d[i][i] < 0 </tex>, и вывести кратчайший путь между парой вершин <tex> (i, i) </tex>. При этом стоит учитывать, что при наличии отрицательного цикла расстояния могут уменьшаться экспоненциально. Для предотвращения переполнения все вычисления стоит ограничивать снизу величиной <tex>-INF</tex>, либо проверять наличие отрицательных чисел на главной диагонали во время подсчета.
+
Из доказательства следует, что для поиска цикла отрицательного веса необходимо, после завершения работы алгоритма, найти вершину <tex> i </tex>, для которой <tex> d[i][i] < 0 </tex>, и вывести кратчайший путь между парой вершин <tex> (i, i) </tex>. При этом стоит учитывать, что при наличии отрицательного цикла расстояния могут уменьшаться экспоненциально. Для предотвращения переполнения все вычисления стоит ограничивать снизу величиной <tex>-\infty</tex>, либо проверять наличие отрицательных чисел на главной диагонали во время подсчета.
== Литература ==
+
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
+
== Построение транзитивного замыкания ==
 +
Сформулируем нашу задачу в терминах графов: рассмотрим граф <tex>G=(V,\; E),\; |V| = n</tex>, соответствующий отношению <tex>R</tex>. Тогда необходимо найти все пары вершин <tex>(x, y) </tex>, соединенных некоторым путем.
 +
Иными словами, требуется построить новое отношение <tex>T</tex>, которое будет состоять из всех пар <tex>(x, y) </tex> таких, что найдется последовательность <tex>x = x_0, x_1, \dots, x_k = y </tex>, где <tex> (x_{i-1}, x_i) \in R, i = 1, 2, \dots, k </tex>.
 +
 
 +
=== Псевдокод ===
 +
Изначально матрица <tex>W</tex> заполняется соответственно отношению <tex>R</tex>, то есть <tex>W[i][j] = [(i, j) \in R] </tex>. Затем внешним циклом перебираются все элементы <tex>k</tex> множества <tex>X</tex> и для каждого из них, если он может использоваться, как промежуточный для соединения двух элементов <tex>i</tex> и <tex>j</tex>, отношение <tex>T</tex> расширяется добавлением в него пары <tex>(i, j)</tex>.
 +
 
 +
'''for''' k = 1 '''to''' n
 +
    '''for''' i = 1 '''to''' n
 +
        '''for''' j = 1 '''to''' n
 +
            W[i][j] = W[i][j] '''or''' (W[i][k] '''and''' W[k][j])
 +
=== Доказательство === 
 +
<wikitex>Назовем ''промежуточной'' вершину некоторого пути $p = \left \langle v_0, v_1, \dots, v_k \right \rangle$, принадлежащую множеству вершин этого пути и отличающуюся от начальной и конечной вершин, то есть принадлежащую $\left \{ v_1, v_2, \dots, v_{k-1} \right \}$. Рассмотрим произвольную пару вершин $i, j \in V$ и все пути между ними, промежуточные вершины которых принадлежат множеству вершин с номерами $\left \{ 1, 2, \dots, k \right \}$. Пусть $p$ {{---}} некоторый из этих путей. Докажем по индукции (по числу промежуточных вершин в пути), что после $i$-ой итерации внешнего цикла будет верно утверждение {{---}} если в построенном графе между выбранной парой вершин есть путь, содержащий в качестве промежуточных только вершины из множества вершин с номерами $\left \{ v_1, v_2, \dots, v_{i} \right \}$, то между ними будет ребро.
 +
 
 +
* База индукции. Если у нас нет промежуточных вершин, что соответствует начальной матрице смежности, то утверждение выполнено: либо есть ребро (путь не содержит промежуточных вершин), либо его нет.
 +
* Индуктивный переход. Пусть предположение выполнено для $i = k - 1$. Докажем, что оно верно и для $i = k$ Рассмотрим случаи (далее под вершиной будем понимать ее номер для простоты изложения):
 +
** $k$ не является промежуточной вершиной пути $p$. Тогда все его промежуточные пути принадлежат множеству вершин с номерами $\left \{ 1, 2, \dots, k-1 \right \} \subset \left \{ 1, 2, \dots, k \right \}$, то есть существует путь с промежуточными вершинами в исходном множестве. Это значит $W[i][j]$ будет истиной. В противном случае $W[i][j]$ будет ложью и на k-ом шаге ею и останется.
 +
** $k$ является промежуточной вершиной предполагаемого пути $p$. Тогда этот путь можно разбить на два пути: $i \xrightarrow{p_1} k \xrightarrow{p_2} j$. Пусть как $p_1$, так и $p_2$ существуют. Тогда они содержат в качестве промежуточных вершины из множества $\left \{ 1, 2, \dots, k-1 \right \} \subset \left \{ 1, 2, \dots, k \right \}$ (так как вершина $k$ {{---}} либо конечная, либо начальная, то она не может быть в множестве по нашему определению). Тогда $W[i][k]$ и $W[k][j]$ истинны и по индуктивному предположению посчитаны верно. Тогда и $W[i][j]$ тоже истина. Пусть какого-то пути не существует. Тогда пути $p$ тоже не может существовать, так как добраться, например, от вершины $i$ до $k$ по вершинам из множества $\left \{ 1, 2, \dots, k \right \}$ невозможно по индуктивному предположению. Тогда вся конъюнкция будет ложной, то есть такого пути нет, откуда $W[i][j]$ после итерации будет ложью.
 +
 
 +
Таким образом, после завершения внешнего цикла у нас будет $W[i][j] = true$, если между этими вершинами есть путь, содержащий в качестве промежуточных вершин из множества всех остальных вершин графа, что и есть транзитивное замыкание.
 +
</wikitex>
 +
=== Оптимизация с помощью битовых масок ===
 +
Строки матрицы <tex>W</tex> можно хранить с помощью массива битовых масок длиной <tex>k</tex>. Тогда последний цикл будет выполняться в <tex>k</tex> раз быстрее и сложность алгоритма снижается до <tex>O\Big(\dfrac{n^3}{k}\Big)</tex>. <br>
 +
Пример реализации оптимизации с помощью битмасок:
 +
 +
'''unsigned int''' W[N][N / 32 + 1]         
 +
 +
'''func''' transitiveClosure(W)''':'''
 +
    '''for''' k = 1 '''to''' n
 +
        '''for''' i = 1 '''to''' n
 +
            '''if''' бит с номером ''(k % 32)'' в маске ''a[i][k / 32]'' единичный
 +
                '''for''' j = 1 '''to''' n / 32 + 1
 +
                    W[i][j] = W[i][j] '''or''' W[k][j]
 +
 
 +
В данной реализации длина битовой маски <tex>k</tex> равна <tex>32</tex> битам. Последний цикл делает в <tex>32</tex> раза меньше операций {{---}} сложность алгоритма <tex>O\Big(\dfrac{n^3}{32}\Big)</tex>.
 +
 
 +
== Источники информации ==
 +
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ 2-е изд — М.: Издательский дом «Вильямс», 2009. — ISBN 978-5-8459-0857-5.
 +
* Романовский И. В. Дискретный анализ: Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. Изд. 3-е. — СПб.: Невский диалект, 2003. — 320 с. — ISBN 5-7940-0114-3.
 +
* [https://ru.wikipedia.org/wiki/Алгоритм_Флойда_—_Уоршелла Википедия - Алгоритм Флойда — Уоршелла]
 +
* [https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm Wikipedia - Floyd–Warshall algorithm]
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Кратчайшие пути в графах ]]
 
[[Категория: Кратчайшие пути в графах ]]

Текущая версия на 19:39, 4 сентября 2022

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

Алгоритм

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

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

Дан взвешенный ориентированный граф [math] G(V, E) [/math], в котором вершины пронумерованы от [math]1[/math] до [math]n[/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] 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 [math]i \in V[/math]
    for [math]u \in V[/math]
        for [math]v \in V[/math]
            [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 = [math]\omega[/math]                // изначально [math]d = \omega[/math]
    for [math]i \in V[/math]
        for [math]u \in V[/math]
            for [math]v \in V[/math]
                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]
0.png Floyd 1.png Floyd 2.png Floyd algo 3.png Floyd 4.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[/math], в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из [math]u[/math] в [math]v[/math] по кратчайшему пути.

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

func floyd(w):
    d = [math]\omega[/math]               // изначально [math]d = \omega[/math]
    for [math]i \in V[/math]
        for [math]u \in V[/math]
            for [math]v \in V[/math]
                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]
func getShortestPath(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]-\infty[/math], либо проверять наличие отрицательных чисел на главной диагонали во время подсчета.

Построение транзитивного замыкания

Сформулируем нашу задачу в терминах графов: рассмотрим граф [math]G=(V,\; E),\; |V| = n[/math], соответствующий отношению [math]R[/math]. Тогда необходимо найти все пары вершин [math](x, y) [/math], соединенных некоторым путем. Иными словами, требуется построить новое отношение [math]T[/math], которое будет состоять из всех пар [math](x, y) [/math] таких, что найдется последовательность [math]x = x_0, x_1, \dots, x_k = y [/math], где [math] (x_{i-1}, x_i) \in R, i = 1, 2, \dots, k [/math].

Псевдокод

Изначально матрица [math]W[/math] заполняется соответственно отношению [math]R[/math], то есть [math]W[i][j] = [(i, j) \in R] [/math]. Затем внешним циклом перебираются все элементы [math]k[/math] множества [math]X[/math] и для каждого из них, если он может использоваться, как промежуточный для соединения двух элементов [math]i[/math] и [math]j[/math], отношение [math]T[/math] расширяется добавлением в него пары [math](i, j)[/math].

for k = 1 to n
    for i = 1 to n
        for j = 1 to n
            W[i][j] = W[i][j] or (W[i][k] and W[k][j])

Доказательство

<wikitex>Назовем промежуточной вершину некоторого пути $p = \left \langle v_0, v_1, \dots, v_k \right \rangle$, принадлежащую множеству вершин этого пути и отличающуюся от начальной и конечной вершин, то есть принадлежащую $\left \{ v_1, v_2, \dots, v_{k-1} \right \}$. Рассмотрим произвольную пару вершин $i, j \in V$ и все пути между ними, промежуточные вершины которых принадлежат множеству вершин с номерами $\left \{ 1, 2, \dots, k \right \}$. Пусть $p$ — некоторый из этих путей. Докажем по индукции (по числу промежуточных вершин в пути), что после $i$-ой итерации внешнего цикла будет верно утверждение — если в построенном графе между выбранной парой вершин есть путь, содержащий в качестве промежуточных только вершины из множества вершин с номерами $\left \{ v_1, v_2, \dots, v_{i} \right \}$, то между ними будет ребро.

  • База индукции. Если у нас нет промежуточных вершин, что соответствует начальной матрице смежности, то утверждение выполнено: либо есть ребро (путь не содержит промежуточных вершин), либо его нет.
  • Индуктивный переход. Пусть предположение выполнено для $i = k - 1$. Докажем, что оно верно и для $i = k$ Рассмотрим случаи (далее под вершиной будем понимать ее номер для простоты изложения):
    • $k$ не является промежуточной вершиной пути $p$. Тогда все его промежуточные пути принадлежат множеству вершин с номерами $\left \{ 1, 2, \dots, k-1 \right \} \subset \left \{ 1, 2, \dots, k \right \}$, то есть существует путь с промежуточными вершинами в исходном множестве. Это значит $W[i][j]$ будет истиной. В противном случае $W[i][j]$ будет ложью и на k-ом шаге ею и останется.
    • $k$ является промежуточной вершиной предполагаемого пути $p$. Тогда этот путь можно разбить на два пути: $i \xrightarrow{p_1} k \xrightarrow{p_2} j$. Пусть как $p_1$, так и $p_2$ существуют. Тогда они содержат в качестве промежуточных вершины из множества $\left \{ 1, 2, \dots, k-1 \right \} \subset \left \{ 1, 2, \dots, k \right \}$ (так как вершина $k$ — либо конечная, либо начальная, то она не может быть в множестве по нашему определению). Тогда $W[i][k]$ и $W[k][j]$ истинны и по индуктивному предположению посчитаны верно. Тогда и $W[i][j]$ тоже истина. Пусть какого-то пути не существует. Тогда пути $p$ тоже не может существовать, так как добраться, например, от вершины $i$ до $k$ по вершинам из множества $\left \{ 1, 2, \dots, k \right \}$ невозможно по индуктивному предположению. Тогда вся конъюнкция будет ложной, то есть такого пути нет, откуда $W[i][j]$ после итерации будет ложью.

Таким образом, после завершения внешнего цикла у нас будет $W[i][j] = true$, если между этими вершинами есть путь, содержащий в качестве промежуточных вершин из множества всех остальных вершин графа, что и есть транзитивное замыкание. </wikitex>

Оптимизация с помощью битовых масок

Строки матрицы [math]W[/math] можно хранить с помощью массива битовых масок длиной [math]k[/math]. Тогда последний цикл будет выполняться в [math]k[/math] раз быстрее и сложность алгоритма снижается до [math]O\Big(\dfrac{n^3}{k}\Big)[/math].
Пример реализации оптимизации с помощью битмасок:

unsigned int W[N][N / 32 + 1]           

func transitiveClosure(W):
    for k = 1 to n
        for i = 1 to n
            if бит с номером (k % 32) в маске a[i][k / 32] единичный
                for j = 1 to n / 32 + 1
                    W[i][j] = W[i][j] or W[k][j]

В данной реализации длина битовой маски [math]k[/math] равна [math]32[/math] битам. Последний цикл делает в [math]32[/math] раза меньше операций — сложность алгоритма [math]O\Big(\dfrac{n^3}{32}\Big)[/math].

Источники информации

  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд — М.: Издательский дом «Вильямс», 2009. — ISBN 978-5-8459-0857-5.
  • Романовский И. В. Дискретный анализ: Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. Изд. 3-е. — СПб.: Невский диалект, 2003. — 320 с. — ISBN 5-7940-0114-3.
  • Википедия - Алгоритм Флойда — Уоршелла
  • Wikipedia - Floyd–Warshall algorithm