Изменения

На каждом шаге алгоритма, мы будем брать очередную вершину (пусть её номер {{---}} <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)}_{uv} = w </tex> # Основная часть '''for ''' i in {= 1..'''to''' n}: '''for ''' u in {= 1..'''to''' n}: '''for ''' v in {= 1..'''to''' n}: <tex dpi = "105" > d^{(i)}_{uv} = \min(d^{(i - 1)}_{uv}, d^{(i - 1)}_{ui} + d^{(i - 1)}_{iv}) </tex>

Утверждается, что можно избавиться от одной размерности в массиве <tex> d </tex>, т.е. использовать двумерный массив <tex>d_{uv}</tex>. В процессе работы алгоритма поддерживается инвариант <tex>\rho(u, v) \le leqslant d_{uv} \le leqslant d_{uv}^{(i)}</tex>, а, поскольку, после выполнения работы алгоритма <tex> \rho(u, v) == d_{uv}^{(i)} </tex>, то тогда будет выполняться и <tex> \rho(u, v) == d_{uv} </tex>.

В течение работы алгоритма Флойда выполняются неравенства: <tex>\rho(u, v) \le leqslant d_{uv} \le leqslant d_{uv}^{(i)}</tex>.

Покажем, что <tex> d_{uv} \le leqslant d_{uv}^{(i)} </tex>, зная, что <tex> d'_{uv} \le leqslant d_{uv}^{(i - 1)} </tex>.

* Значение <tex> d_{uv}^{(i)} </tex> стало меньше, чем <tex> d_{uv}^{(i - 1)} </tex>. Тогда <tex> d_{uv}^{(i)} = d_{ui}^{(i-1)} + d_{iv}^{(i-1)} \ge geqslant </tex> (выполняется на шаге <tex> i - 1 </tex>, по индукционному предположению) <tex> \ge geqslant d'_{ui} + d'_{iv} \ge</tex> (в силу выполнения 7-ой строчки алгоритма на <tex>i</tex>-ой итерации и невозрастания элементов массива <tex> d </tex>) <tex>\ge geqslant d_{uv}</tex>.* В ином случае всё очевидно: <tex> d_{uv}^{(i)} = d_{uv}^{(i - 1)} \ge geqslant d'_{uv} \ge geqslant d_{uv} </tex>, и неравенство тривиально.

Пусть неравенство было нарушено, рассмотрим момент, когда оно было нарушено впервые. Пусть это была <tex>i</tex>-ая итерация и в этот момент изменилось значение <tex>d_{uv}</tex> и выполнилось <tex>\rho(u,v) > d_{uv}</tex>. Так как <tex>d_{uv}</tex> изменилось, то <tex>d_{uv} = d_{ui} + d_{iv} \ge</tex> (так как ранее <tex>\forall u, v \in V: \rho(u,v) \le leqslant d_{uv}</tex>) <tex>\ge geqslant \rho(u, i) + \rho(i, v) \ge</tex> (по неравенству треугольника) <tex>\ge geqslant \rho(u, v)</tex>. Итак <tex>d_{uv} \ge geqslant \rho(u,v)</tex> {{---}} противоречие.

# Инициализация '''func''' floyd(w)''':''' <tex dpi = "105"> d = w </tex> # Основная часть '''for ''' i in {= 1..'''to''' n}: '''for ''' u in {= 1..'''to''' n}: '''for ''' v in {= 1..'''to''' n}: <tex dpi = "105"> d_{uv} d[u][v] = min(d_{uv}d[u][v], d_{ui} d[u][i] + d_{iv}d[i][v]) </tex>

Алгоритм Флойда легко модифицировать таким образом, чтобы он возвращал не только длину кратчайшего пути, но и сам путь. Для этого достаточно завести дополнительный массив <tex>next_{uv}next</tex>, в котором будет храниться номер вершины, в которую надо пойти следующей, чтобы дойти из <tex>u</tex> в <tex>v</tex> по кратчайшему пути.

'''func''' floyd(w)''':''' # Инициализация d = w t[u][v] = v если есть ребро uv # Основная часть '''for ''' i in {= 1..'''to''' n}: '''for ''' u in {= 1..'''to''' n}: '''for ''' v in {= 1..'''to''' n}: '''if (''' d[u][i] + d[i][v]) < d[u][v]: d[u][v] = d[u][i] + d[i][v] next[u][v] = i

# Вывод кратчайшего пути def '''func''' get_shortest_path(u, v)''':''' '''if ''' d[u][v] == inf:<tex>\infty</tex> raise NoPath # Из '''print''' "No path found" <font color="green">// между вершинами u в и v нет пути нет</font> c = u '''while ''' c != v: '''print ''' c c = next[c][v] '''print ''' v

* ''Кормен, Томас Х., ЛейзерсонКормен, Чарльз И., РивестЛейзерсон, Рональд Л.Ривест, Клиффорд Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', — 2-е издание. Пер. с англ. изд — М.:Издательский дом "Вильямс"«Вильямс», 2010. — 1296 с.: ил. — Парал. тит. англ2009. — ISBN 978-5-8459-0857-5 (рус.)* [https://ru.wikipedia.org/wiki/Алгоритм_Флойда_—_Уоршелла Википедия - Алгоритм Флойда — Уоршелла]* [https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm Wikipedia - Floyd–Warshall algorithm]