35
правок
Изменения
→Код (окончательный)
|proof=
После инициализации все неравенства, очевидно, выполняются. Далее, массив <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} \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_{ui} + d_{uv} \ge d_{uv} </tex>.
#* В ином случае всё очевидно: <tex> d_{uv}^{(i)} = d_{uv}^{(i - 1)} \ge d_{uv} </tex>, и неравенство тривиально.
