Алгоритм Флойда

Эта статья находится в разработке!

Алгоритм Флойда (алгоритм Флойда–Уоршелла) — динамический алгоритм нахождения длин кратчайших путей между всеми парами вершин взвешенного ориентированного графа. Разработан в 1962 году.

Алгоритм

Пусть дан граф [math]G(V,E)[/math]; [math]\omega_{uv} = \begin{cases} \text{weight of }uv ,& \text{if } uv \in E \\ +\infty ,& \text{if } uv \notin E \end{cases}[/math]; вершины пронумерованы от [math]1[/math] до [math]n[/math].

Обозначим длину кратчайшего пути между вершинами [math]u[/math] и [math]v[/math], содержащего, помимо самих вершин [math]u[/math] и [math]v[/math], только вершины с номерами [math]1 .. i[/math] как [math]d_{uv}^i[/math]. Понятно, что [math]d_{uv}^0 = \omega_{uv}[/math].