Изменения
Восстановление правильного кода
[[Файл:Floyd_first.png|right|thumb|180px|Текущий (синий) путь и потенциально более короткий (красный)]]
Дан взвешенный ориентированный [[Основные определения: граф , ребро, вершина, степень, петля, путь, цикл|граф]] <tex> G(V, E) </tex>; , в котором вершины пронумерованы от <tex>1</tex> до <tex>n</tex>. <tex>\omega_{uv} =
\begin{cases}
\text{weight of }uv ,& \text{if } uv \in E \\
+\infty ,& \text{if } uv \notin E
\end{cases}</tex>, в котором вершины пронумерованы от <texbr>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>.
=== Описание ===
'''func''' floyd(w)''':'''
d = w<tex>\omega</tex> <font color="green">// изначально <tex>d = \omega</tex></font>
'''for''' <tex>i \in V</tex>
'''for''' <tex>u \in V</tex>
=== Модифицированный алгоритм ===
'''func''' floyd(w)''':'''
d = w<tex>\omega</tex> <font color="green">// изначально <tex>d = \omega</tex></font>
'''for''' <tex>i \in V</tex>
'''for''' <tex>u \in V</tex>
'''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)''':'''
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(\fracdfrac{n^3}{k}\Big)</tex>. <br>Пример реализации оптимизации с использованием массива чисел типа ''unsigned int''помощью битмасок:
'''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>.
== Источники информации ==
