Изменения

Перейти к: навигация, поиск

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

101 байт добавлено, 08:49, 17 января 2012
Нет описания правки
'''Докажем второе неравенство индукцией по итерациям алгоритма.'''
Пусть также <tex>d'_{uv}</tex> {{--- }} значение <tex>d_{uv}</tex> сразу после <tex>i - 1</tex> итерации. Покажем, что <tex> d_{uv} \le d_{uv}^{(i)} </tex>, зная, что <tex> d'_{uv} \le 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 </tex> (выполняется на шаге <tex> i - 1 </tex>, по индукционному предположению) <tex> \ge d'_{ui} + d'_{iv} \ge</tex> (в силу выполнения 7-ой строчки алгоритма на <tex>i</tex>-ой итерации и невозрастания элементов массива <tex> d </tex>) <tex>\ge d_{uv}</tex>.
* В ином случае всё очевидно: <tex> d_{uv}^{(i)} = d_{uv}^{(i - 1)} \ge d'_{uv} \ge d_{uv} </tex>, и неравенство тривиально.
Анонимный участник

Навигация