Алгоритм Флойда — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показано 10 промежуточных версий 3 участников) | |||
Строка 6: | Строка 6: | ||
[[Файл:Floyd_first.png|right|thumb|180px|Текущий (синий) путь и потенциально более короткий (красный)]] | [[Файл:Floyd_first.png|right|thumb|180px|Текущий (синий) путь и потенциально более короткий (красный)]] | ||
− | Дан взвешенный ориентированный граф <tex> G(V, E) </tex> | + | Дан взвешенный ориентированный [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|граф]] <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> | + | \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>. |
=== Описание === | === Описание === | ||
Строка 20: | Строка 22: | ||
=== Код (в первом приближении) === | === Код (в первом приближении) === | ||
<tex>d^{(0)}_{uv} = w</tex> | <tex>d^{(0)}_{uv} = w</tex> | ||
− | '''for''' i | + | '''for''' <tex>i \in V</tex> |
− | '''for''' u | + | '''for''' <tex>u \in V</tex> |
− | '''for''' v | + | '''for''' <tex>v \in V</tex> |
<tex> d^{(i)}_{uv} = \min(d^{(i - 1)}_{uv}, d^{(i - 1)}_{ui} + d^{(i - 1)}_{iv}) </tex> | <tex> d^{(i)}_{uv} = \min(d^{(i - 1)}_{uv}, d^{(i - 1)}_{ui} + d^{(i - 1)}_{iv}) </tex> | ||
Строка 55: | Строка 57: | ||
'''func''' floyd(w)''':''' | '''func''' floyd(w)''':''' | ||
− | d = | + | d = <tex>\omega</tex> <font color="green">// изначально <tex>d = \omega</tex></font> |
− | '''for''' i | + | '''for''' <tex>i \in V</tex> |
− | '''for''' u | + | '''for''' <tex>u \in V</tex> |
− | '''for''' v | + | '''for''' <tex>v \in V</tex> |
d[u][v] = min(d[u][v], d[u][i] + d[i][v]) | d[u][v] = min(d[u][v], d[u][i] + d[i][v]) | ||
Строка 106: | Строка 108: | ||
=== Модифицированный алгоритм === | === Модифицированный алгоритм === | ||
'''func''' floyd(w)''':''' | '''func''' floyd(w)''':''' | ||
− | d = | + | d = <tex>\omega</tex> <font color="green">// изначально <tex>d = \omega</tex></font> |
− | '''for''' i | + | '''for''' <tex>i \in V</tex> |
− | '''for''' u | + | '''for''' <tex>u \in V</tex> |
− | '''for''' v | + | '''for''' <tex>v \in V</tex> |
'''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] | ||
− | next[u][v] = i | + | next[u][v] = next[u][i] |
− | '''func''' | + | '''func''' getShortestPath(u, v)''':''' |
'''if''' d[u][v] == <tex>\infty</tex> | '''if''' d[u][v] == <tex>\infty</tex> | ||
'''print''' "No path found" <font color="green">// между вершинами u и v нет пути</font> | '''print''' "No path found" <font color="green">// между вершинами u и v нет пути</font> | ||
Строка 130: | Строка 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>- | + | Из доказательства следует, что для поиска цикла отрицательного веса необходимо, после завершения работы алгоритма, найти вершину <tex> i </tex>, для которой <tex> d[i][i] < 0 </tex>, и вывести кратчайший путь между парой вершин <tex> (i, i) </tex>. При этом стоит учитывать, что при наличии отрицательного цикла расстояния могут уменьшаться экспоненциально. Для предотвращения переполнения все вычисления стоит ограничивать снизу величиной <tex>-\infty</tex>, либо проверять наличие отрицательных чисел на главной диагонали во время подсчета. |
− | == | + | |
+ | == Построение транзитивного замыкания == | ||
+ | Сформулируем нашу задачу в терминах графов: рассмотрим граф <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. | * Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд — М.: Издательский дом «Вильямс», 2009. — ISBN 978-5-8459-0857-5. | ||
+ | * Романовский И. В. Дискретный анализ: Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. Изд. 3-е. — СПб.: Невский диалект, 2003. — 320 с. — ISBN 5-7940-0114-3. | ||
* [https://ru.wikipedia.org/wiki/Алгоритм_Флойда_—_Уоршелла Википедия - Алгоритм Флойда — Уоршелла] | * [https://ru.wikipedia.org/wiki/Алгоритм_Флойда_—_Уоршелла Википедия - Алгоритм Флойда — Уоршелла] | ||
* [https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm Wikipedia - Floyd–Warshall algorithm] | * [https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm Wikipedia - Floyd–Warshall algorithm] |
Текущая версия на 19:39, 4 сентября 2022
Алгоритм Флойда (алгоритм Флойда–Уоршелла) — алгоритм нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а в случае, когда такой цикл есть, позволяет найти хотя бы один такой цикл. Алгоритм работает за
времени и использует памяти. Разработан в 1962 году.Содержание
Алгоритм
Постановка задачи
Дан взвешенный ориентированный граф , в котором вершины пронумерованы от до .
Требуется найти матрицу кратчайших расстояний , в которой элемент либо равен длине кратчайшего пути из в , либо равен , если вершина не достижима из .
Описание
Обозначим длину кратчайшего пути между вершинами
и , содержащего, помимо и , только вершины из множества как , .На каждом шаге алгоритма, мы будем брать очередную вершину (пусть её номер —
) и для всех пар вершин и вычислять . То есть, если кратчайший путь из в , содержащий только вершины из множества , проходит через вершину , то кратчайшим путем из в является кратчайший путь из в , объединенный с кратчайшим путем из в . В противном случае, когда этот путь не содержит вершины , кратчайший путь из в , содержащий только вершины из множества является кратчайшим путем из в , содержащим только вершины из множества .Код (в первом приближении)
for for for
В итоге получаем, что матрица
и является искомой матрицей кратчайших путей, поскольку содержит в себе длины кратчайших путей между всеми парами вершин, имеющих в качестве промежуточных вершин вершины из множества , что есть попросту все вершины графа. Такая реализация работает за времени и использует памяти.Код (окончательный)
Утверждается, что можно избавиться от одной размерности в массиве
, т.е. использовать двумерный массив . В процессе работы алгоритма поддерживается инвариант , а, поскольку, после выполнения работы алгоритма , то тогда будет выполняться и .Утверждение: |
В течение работы алгоритма Флойда выполняются неравенства: . |
После инициализации все неравенства, очевидно, выполняются. Далее, массив может измениться только в строчке 5.Докажем второе неравенство индукцией по итерациям алгоритма. Пусть также — значение сразу после итерации.Покажем, что , зная, что .Рассмотрим два случая:
Пусть неравенство было нарушено, рассмотрим момент, когда оно было нарушено впервые. Пусть это была Итак -ая итерация и в этот момент изменилось значение и выполнилось . Так как изменилось, то (так как ранее ) (по неравенству треугольника) . — противоречие. |
func floyd(w): d =// изначально for for for d[u][v] = min(d[u][v], d[u][i] + d[i][v])
Данная реализация работает за время
, но требует уже памяти. В целом, алгоритм Флойда очень прост, и, поскольку в нем используются только простые операции, константа, скрытая в определении весьма мала.Пример работы
![]() |
![]() |
![]() |
![]() |
![]() |
Вывод кратчайшего пути
Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив
, в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из в по кратчайшему пути.Модифицированный алгоритм
func floyd(w): d =// изначально for for for 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] ==
print "No path found" // между вершинами u и v нет пути
c = u
while c != v
print c
c = next[c][v]
print v
Нахождение отрицательного цикла
Утверждение: |
При наличии цикла отрицательного веса в матрице появятся отрицательные числа на главной диагонали. |
Так как алгоритм Флойда последовательно релаксирует расстояния между всеми парами вершин | , в том числе и теми, у которых , а начальное расстояние между парой вершин равно нулю, то релаксация может произойти только при наличии вершины такой, что , что эквивалентно наличию отрицательного цикла, проходящего через вершину .
Из доказательства следует, что для поиска цикла отрицательного веса необходимо, после завершения работы алгоритма, найти вершину
, для которой , и вывести кратчайший путь между парой вершин . При этом стоит учитывать, что при наличии отрицательного цикла расстояния могут уменьшаться экспоненциально. Для предотвращения переполнения все вычисления стоит ограничивать снизу величиной , либо проверять наличие отрицательных чисел на главной диагонали во время подсчета.Построение транзитивного замыкания
Сформулируем нашу задачу в терминах графов: рассмотрим граф
, соответствующий отношению . Тогда необходимо найти все пары вершин , соединенных некоторым путем. Иными словами, требуется построить новое отношение , которое будет состоять из всех пар таких, что найдется последовательность , где .Псевдокод
Изначально матрица
заполняется соответственно отношению , то есть . Затем внешним циклом перебираются все элементы множества и для каждого из них, если он может использоваться, как промежуточный для соединения двух элементов и , отношение расширяется добавлением в него пары .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>
Оптимизация с помощью битовых масок
Строки матрицы
Пример реализации оптимизации с помощью битмасок:
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]
В данной реализации длина битовой маски
равна битам. Последний цикл делает в раза меньше операций — сложность алгоритма .Источники информации
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд — М.: Издательский дом «Вильямс», 2009. — ISBN 978-5-8459-0857-5.
- Романовский И. В. Дискретный анализ: Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. Изд. 3-е. — СПб.: Невский диалект, 2003. — 320 с. — ISBN 5-7940-0114-3.
- Википедия - Алгоритм Флойда — Уоршелла
- Wikipedia - Floyd–Warshall algorithm