Изменения

После инициализации все неравенства, очевидно, выполняются. Далее, массив <tex> d </tex> может измениться только в строчке 5. Докажем оба неравенства индукцией по итерациям алгоритма. Пусть также <tex>d'_{uv}</tex> - значение <tex>d_{uv}</tex> сразу после <tex>i - 1</tex> итерации.

# <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 - 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} </tex>, и неравенство тривиально.'