Бюрократы, editor, Администраторы
422
правки
Изменения
Начинаем
{{В разработке}}
'''Алгоритм Флойда (алгоритм Флойда–Уоршелла)''' — динамический алгоритм нахождения длин кратчайших путей между всеми парами вершин взвешенного ориентированного графа. Разработан в 1962 году.
== Алгоритм ==
Пусть дан граф <tex>G(V,E)</tex>; <tex>\omega_{uv} =
\begin{cases}
\text{weight of }uv ,& \text{if } uv \in E \\
+\infty ,& \text{if } uv \notin E
\end{cases}</tex>; вершины пронумерованы от <tex>1</tex> до <tex>n</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>.
'''Алгоритм Флойда (алгоритм Флойда–Уоршелла)''' — динамический алгоритм нахождения длин кратчайших путей между всеми парами вершин взвешенного ориентированного графа. Разработан в 1962 году.
== Алгоритм ==
Пусть дан граф <tex>G(V,E)</tex>; <tex>\omega_{uv} =
\begin{cases}
\text{weight of }uv ,& \text{if } uv \in E \\
+\infty ,& \text{if } uv \notin E
\end{cases}</tex>; вершины пронумерованы от <tex>1</tex> до <tex>n</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>.
