188
правок
Изменения
м
Нет описания правки
[[Файл: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>
</wikitex>
=== Оптимизация с помощью битовых масок ===
Строки матрицы <tex>W</tex> можно хранить с помощью массива битовых маск длиной <tex>k</tex>. Тогда последний цикл будет выполняться в <tex>k</tex> раз быстрее и сложность алгоритма снижается до <tex>O(\frac{n^3}{k})</tex>. <br>Пример реализации оптимизации с использованием массива чисел типа ''unsigned int''помощью битмасок:
'''unsigned int''' W[N][N / 32 + 1]
