Изменения

::Предположим, что <tex>d'[u] + \omega(vu) \geqslant \omega(Path(s \to v) \circ (vu))</tex>, то есть вес любого найденного пути больше чем <tex>\rho(s, u)</tex>.::Переходим ко второму неравенству, когда <tex>d'[u]</tex> изменилось.::<tex>d'[u] \leqslant \min\limits_{i = 0..k} d[i][u]</tex> выполняется, так как <tex>d'[u]</tex> могло только уменьшится, то это неравенство выполняется.::Теперь возможно два случая:::#<tex>\min\limits_{i = 0..k-1} d[i][u] = d[k+1][u]</tex>::#<tex>\min\limits_{i = 0..k-1} d[i][u] = \min\limits_{i = j} d[j][u]</tex><br><br>::Рассмотрим 1 случай::::<tex>\min\limits_{i = 0..k-1} d[i][u] = d[k+1][u]</tex><br>:::<tex>d'[u] \leqslant d'[v] + \omega(vu) \leqslant d[k][v] + \omega(vu) = d[k+1][u]</tex>::<tex>\vartriangleleft</tex>::2 случай расписывается аналогично.