Изменения

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

Пусть дан === Постановка задачи === Дан взвешенный ориентированный граф <tex>G(V,E)</tex>; <tex>\omega_{uv} =

\end{cases}</tex>; , в котором вершины пронумерованы от <tex>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>. === Описание ===

Обозначим длину кратчайшего пути между вершинами <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 dpi = "105"> d[^{(0] )} = w</tex>

<tex dpi = "105" > 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) \le d_{uv} \le d_{uv}^i</tex>, а значит <tex>d_{uv}</tex> тоже в итоге сойдутся к решению.