205
правок
Изменения
м
→Сохранение кратчайших путей
:<tex>P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k </tex>
:<tex>w_\phi(P) = w_\phi(u_0u_1) + w_\phi(u_1u_2) + ... + w_\phi(u_{k-1}u_k) = \phi(u_0) + w(u_0u_1) - \phi(u_1) + ... </tex> <tex>- \phi(u_{k-1}) + \phi(u_{k-1}) + w(u_{k-1}u_k) - \phi(u_k) = </tex> <tex>=\phi(u_0) + w(P) - \phi(u_k)</tex>
:<tex>w_\phi(P) < w_\phi(Q)</tex>
