Алгоритм Джонсона

Сохранение кратчайших путей

Пусть задана потенциальная функция: [math]\phi: V \rightarrow \mathbb{R}. [/math] Введем обозначение [math] w_\phi(uv) = w(uv) + \phi(u) - \phi(v), \; uv \in E. [/math]

Лемма:

Пусть [math]P,\; Q : a \rightsquigarrow b.\; w(P) \lt w(Q)[/math]. Тогда [math]\forall \phi: \; w_\phi(P) \lt w_\phi(Q)[/math]

Доказательство:

[math]\triangleright[/math]

[math]P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k [/math] [math]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) + ... + \phi(u_{k-1}) + w(u_{k-1}u_k) - \phi(u_k) = \phi(u_0) + w(P) - \phi(u_k)[/math] [math]w_\phi(P) \lt w_\phi(Q)[/math] [math]w_\phi(P) = \phi(a) + w(P) - \phi(b)[/math] [math]w_\phi(Q) = \phi(a) + w(Q) - \phi(b)[/math] Отсюда, [math]w(P) \lt w(Q)[/math]

[math]\triangleleft[/math]