40
правок
Изменения
м
→Код (окончательный)
#* Значение <tex> d_{uv} </tex> не изменилось. Тогда неравенство выполняется автоматически по индукционному предположению.
# <tex> d_{uv} \le d_{uv}^{(i)} </tex>. Аналогично рассмотрим два случая:
#* Значение <tex> d_{uv}^{(i)} </tex> изменилось. Тогда стало меньше, чем <tex> d_{uv}^{(i)} \ge </tex>. Тогда <tex> d_{uiuv}^{(i-1)} + = d_{ivui}^{(i-1)} \ge d_{ui}^{(i)} + d_{iv}^{(i-1)} \ge d_{ui} + d_{uv} \ge d_{uv} </tex> (выполняется на шаге <tex> i - 1 </tex>, по индукционному предположению и тому факту, что а в силу неубывания элементов массива <tex> d_{uv}^{(i)} d </tex> не возрастает с ростом выполняется и на текущей итерации) <tex> i \ge d_{ui} + d_{uv} \ge d_{uv} </tex>.
#* В ином случае всё очевидно: <tex> d_{uv}^{(i)} = d_{uv}^{(i - 1)} \ge d_{uv} </tex>, и неравенство тривиально.
