Изменения

'''Алгоритм Флойда (алгоритм Флойда–Уоршелла)''' {{В разработке---}}алгоритм нахождения длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Работает корректно, если в графе нет циклов отрицательной величины, а в случае, когда такой цикл есть, позволяет найти хотя бы один такой цикл. Алгоритм работает за <tex> \Theta(n^3) </tex> времени и использует <tex> \Theta(n^2) </tex> памяти. Разработан в 1962 году.

'''== Алгоритм Флойда == === Постановка задачи ===[[Файл:Floyd_first.png|right|thumb|180px|Текущий (синий) путь и потенциально более короткий (красный)]] Дан взвешенный ориентированный [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|граф]] <tex> G(алгоритм Флойда–УоршеллаV, E)''' — динамический алгоритм нахождения длин кратчайших путей между всеми парами вершин взвешенного ориентированного графа. Разработан </tex>, в 1962 годукотором вершины пронумерованы от <tex>1</tex> до <tex>n</tex>.

== Алгоритм ==[[Файл:Floyd.png|right|thumb|Текущий (синий) путь и потенциально более короткий (красный)]]Пусть дан граф <tex>G(V,E)</tex>; <tex>\omega_{uv} =

\end{cases}</tex>; вершины пронумерованы от <br>Требуется найти матрицу кратчайших расстояний <tex> d </tex>, в которой элемент <tex> d_{ij} </tex> либо равен длине кратчайшего пути из <tex> i </tex> в <tex> j </tex>, либо равен <tex> +\infty </tex>, если вершина <tex>1j </tex> до не достижима из <tex>ni </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> 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>d[^{(0] )}_{uv} = w</tex> # Основная часть '''for ''' <tex>i \in {1..n}:V</tex> '''for ''' <tex>u \in {1..n}:V</tex> '''for ''' <tex>v \in {1..n}:V</tex> <tex> d[^{(i][u][v] )}_{uv} = \min(d[^{(i-1][u][v])}_{uv}, d[^{(i-1][u][i] )}_{ui} + d[^{(i-1][i][v])}_{iv}) </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) \leqslant d_{uv} \leqslant d_{uv}^{(i)}</tex>, а, поскольку, после выполнения работы алгоритма <tex> \rho(u, v) = d_{uv}^{(i)} </tex>-того слоя массива используются только значения из , то тогда будет выполняться и <tex> \rho(u, v) = d_{uv} </tex>. {{Утверждение|statement=В течение работы алгоритма Флойда выполняются неравенства: <tex>\rho(u, v) \leqslant d_{uv} \leqslant d_{uv}^{(i-1)}</tex>-го слоя. Таким образом|proof= После инициализации все неравенства, очевидно, выполняются. Далее, от первого индекса вообще можно отказатьсямассив <tex> d </tex> может измениться только в строчке 5.  '''Докажем второе неравенство индукцией по итерациям алгоритма.''' Пусть также <tex>d'_{uv}</tex> {{---}} значение <tex>d_{uv}</tex> сразу после <tex>i - 1</tex> итерации.

# Инициализация d = w # Основная часть for i in Покажем, что <tex> d_{1..nuv}: for u in \leqslant d_{1..nuv}: for v in ^{1..n(i)}: </tex>, зная, что <tex> d[u][v] = min'_{uv} \leqslant d_{uv}^{(d[u][v], d[u][i] + d[i][v]- 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)} \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)} \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) \leqslant d_{uv}</tex>) <tex>\geqslant \rho(u, i) + \rho(i, v) \ge</tex> (по неравенству треугольника) <tex>\geqslant \rho(u, v)</tex>. Итак <tex>d_{uv} \geqslant \rho(u,v)</tex> {{---}} противоречие.}}  '''func''' floyd(w)''':''' d = <tex>\omega</tex> <font color="green">// изначально <tex>d = \omega</tex></font> '''for''' <tex>i \in V</tex> '''for''' <tex>u \in V</tex> '''for''' <tex>v \in V</tex> d[u][v] = min(d[u][v], d[u][i] + d[i][v]) Данная реализация работает за время <tex>O\Theta(Vn^3)</tex> — как не сложно видеть, три вложенных цикла выполняются по но требует уже <tex>\Theta(n^2) </tex> памяти. В целом, алгоритм Флойда очень прост, и, поскольку в нем используются только простые операции, константа, скрытая в определении <tex> \Theta </tex> раз каждыйвесьма мала.

{|class = "wikitable" style="text-align:center;"

|width = "180px"| [[Файл:Floyd_step00.png|170px]] ||width = "180px"| [[Файл:Floyd_step1Floyd_1.png|170px]] ||width = "180px"| [[Файл:Floyd_step2Floyd_2.png|170px]] ||width = "180px"| [[Файл:Floyd_step3Floyd_algo_3.png|170px]] ||width = "180px"| [[Файл:Floyd_step4Floyd_4.png|170px]]

Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив <tex>t_{uv}next</tex>, в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из <tex>u</tex> в <tex>v</tex> по кратчайшему пути.

# Инициализация '''func''' floyd(w)''':''' d = w t[u][v] <tex>\omega</tex> <font color="green">// изначально <tex>d = v если есть ребро uv # Основная часть\omega</tex></font> '''for ''' <tex>i \in {1..n}:V</tex> '''for ''' <tex>u \in {1..n}:V</tex> '''for ''' <tex>v \in {1..n}:V</tex> '''if (''' d[u][i] + d[i][v]) < d[u][v]: d[u][v] = d[u][i] + d[i][v] t next[u][v] = tnext[u][i]  '''func''' getShortestPath(u, v)''':''' '''if''' d[u][v] == <tex>\infty</tex> '''print''' "No path found" <font color="green">// между вершинами u и v нет пути</font> c = u '''while''' c != v '''print''' c c = next[c][v] '''print''' v == Нахождение отрицательного цикла =={{Утверждение|statement=При наличии цикла отрицательного веса в матрице <tex> D </tex> появятся отрицательные числа на главной диагонали.|proof=Так как алгоритм Флойда последовательно релаксирует расстояния между всеми парами вершин <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>-\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>.

# Вывод кратчайшего пути== Источники информации == def get_shortest_path(u* Томас Х. Кормен, v)Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд — М.:Издательский дом «Вильямс», 2009. — ISBN 978-5-8459-0857-5. if d[u][v] == inf* Романовский И. В. Дискретный анализ: raise NoPath # Из u в v пути нет c = u while c != vУчебное пособие для студентов, специализирующихся по прикладной математике и информатике. Изд. 3-е. — СПб.:Невский диалект, 2003. — 320 с. — ISBN 5-7940-0114-3. yield c c = t* [chttps://ru.wikipedia.org/wiki/Алгоритм_Флойда_—_Уоршелла Википедия - Алгоритм Флойда — Уоршелла]* [vhttps://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm Wikipedia - Floyd–Warshall algorithm] yield v

[[ФайлКатегория:Floyd_path.pngАлгоритмы и структуры данных]][[Категория: Кратчайшие пути в графах ]]