Изменения

Утверждается, что можно избавиться от одной размерности в массиве <tex> d </tex>, т.е. использовать двумерный массив <tex>d_{uv}</tex>. В процессе работы алгоритма поддерживается инвариант <tex>\rho(u, v) \le d_{uv} \le d_{uv}^{(i)}</tex>, а значит , поскольку, после выполнения работы алгоритма <tex>\rho(u, v) == d_{uv}^{(i)}</tex> тоже , то тогда будет выполняться и <tex> \rho(u, v) == d_{uv} </tex>. {{Утверждение|statement=В течение работы алгоритма Флойда выполняются неравенства: <tex>\rho(u, v) \le d_{uv} \le d_{uv}^{(i)}</tex>.|proof= После инициализации все неравенства, очевидно, выполняются. Далее, массив <tex> d </tex> может измениться только в итоге сойдутся к решениюстрочке 5. Докажем оба неравенства по индукции по итерациям алгоритма: # <tex> \rho(u, v) \le d_{uv} </tex>. Рассмотрим два случая:#* Значение <tex> d_{uv} </tex> изменилось. Тогда <tex> d_{uv} = d_{ui} + d_{iv} \ge \rho(u, i) + \rho(i, v) \ge \rho(u, v) </tex> (по индукционному предположению и неравенству треугольника для <tex> \rho </tex>).#* Значение <tex> d_{uv} </tex> не изменилось. Тогда неравенство выполняется автоматически по индукционному предположению.# <tex> d_{uv} \le d_{uv}^{(i)} </tex>. Аналогично рассмотрим два случая:#* Значение <tex> d_{uv}^{(i)} </tex> изменилось. Тогда <tex> d_{uv}^{(i)} \ge d_{ui}^{(i-1)} + d_{iv}^{(i-1)} \ge d_{ui}^{(i)} + d_{iv}^{(i)} \ge d_{ui} + d_{uv} \ge d_{uv} </tex>, по индукционному предположению и тому факту, что <tex> d_{uv}^{(i)} </tex> невозрастает с ростом <tex> i </tex>.#* В ином случае всё очевидно: <tex> d_{uv}^{(i)} = d_{uv}^{(i - 1)} \ge d_{uv} </tex>, и неравенство тривиально. }}

<tex dpi = "105"> d = w</tex>

d[u][v] <tex dpi = "105"> d_{uv} = min(d[u][v]d_{uv}, d[u][i] d_{ui} + d[i][v]d_{iv})</tex>

Алгоритм всегда завершит работу Данная реализация работает за время <tex>O\Theta(Vn^3)</tex> — как несложно видеть, три вложенных цикла выполняются по но требует уже <tex>\Theta(n^2) </tex> памяти. В целом, алгоритм Флойда очень прост, и, поскольку в нем используются только простые операции, константа, скрытая в определении <tex> \Theta </tex> раз каждыйвесьма мала.

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

tnext[u][v] = tnext[u][i]

yield print c c = tnext[c][v] yield print v