Изменения

'''Алгоритм Джонсона''' находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа во взвешенном ориентированном графе с положительными или отрицательными ребрамилюбыми весами ребер, но не имеющем отрицательных циклов.

Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин в течение времени <tex> O(V^2 * \log(V) + VE) </tex>. Для разреженных графов этот алгоритм ведет себя асимптотически быстрее алгоритма Флойда. Этот алгоритм либо возвращает матрицу кратчайших расстояний между всеми парами вершин, либо сообщение о том, что в графе существует цикл отрицательной длины.

В этом алгоритме используется метод '''изменения веса''' (англ. reweighting). Суть его заключается в том, что для заданного графа <tex> G </tex> строится новая весовая функция <tex> \hat{omega_\omega} varphi </tex>, неотрицательная для всех ребер графа <tex> G </tex> и сохраняющая кратчайшие пути. Такая весовая функция строится при помощи с помощью так называемой '''потенциальной''' функции.

Утверждается, что если какой-то путь <tex> P </tex> был кратчайшим относительно весовой функции <tex> \omega </tex>, то он будет кратчайшим и относительно новой весовой функции <tex> \hat{omega_\omega} varphi </tex>.

Пусть <tex>P,\; Q : </tex> {{---}} 2 пути <tex> a \rightsquigarrow b\;</tex> и <tex>w\omega(P) < w\omega(Q).</tex> Тогда <tex>\forall \varphi: \; w_\omega_\varphi(P) < w_\omega_\varphi(Q)</tex>

:Рассмотрим путь <tex>w_\varphi(P) = w_: \varphi(u_0u_1) + w_;u_0 \varphi(u_1u_2) + ... + w_\varphi(u_{k-1}u_k) = rightarrow u_1 \varphi(u_0) + w(u_0u_1) - rightarrow u_2 \varphi(u_1) + rightarrow ... + \varphi(u_{k-1}) + w(u_{k-1}u_k) - \varphi(u_k) = \varphi(u_0) + w(P) - \varphi(rightarrow u_k)</tex>

:Его вес с новой весовой функцией равен <tex>w\omega_\varphi(P) < w= \omega_\varphi(u_0u_1) + \omega_\varphi(u_1u_2) + ... + \omega_\varphi(Qu_{k-1}u_k)</tex>.

:Вставим определение функции <tex>w_\omega_\varphi : \omega_\varphi(P) = \varphi(au_0) + w\omega(u_0u_1) - \varphi(Pu_1) + ... + \varphi(u_{k-1}) + \omega(u_{k-1}u_k) - \varphi(bu_k)</tex>

:Заметим, что потенциалы все промежуточных вершин в пути сократятся. <tex>w_\omega_\varphi(QP) = \varphi(au_0) + w\omega(QP) - \varphi(bu_k)</tex>

:По изначальному предположению: <tex>\omega(P) < \omega(Q)</tex>. С новой весовой функцией веса соответствующих путей будут:  :<tex>\omega_\varphi(P) = \varphi(a) + \omega(P) - \varphi(b)</tex> :<tex>\omega_\varphi(Q) = \varphi(a) + \omega(Q) - \varphi(b)</tex> :Отсюда, <tex>w_\omega_\varphi(P) < w_\omega_\varphi(Q)</tex>

 В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; w_\omega_\varphi(uv) \ge 0 </tex> 

Рассмотрим произвольный <tex>\Leftarrow </tex>:<tex>w(C) = w_\varphi(C) </tex> - \sum\limits_{uv \in C} (\varphi(u) - \varphi(v))= w_\varphi(C) \ge 0цикл в графе <tex>G</tex>

<tex>\Rightarrow </tex>: Добавим вершину <tex>s</tex> в графПо лемме, соединим её со всеми вершинами графа его вес равен <tex>G</tex> ребрами весом <tex>w \omega(C) = \omega_\varphi(C) - \varphi(u_0) - \varphi(u_0) = \omega_\varphi(C) \ge 0</tex>.

<tex>\Rightarrow </tex>:''Обозначение'' : Добавим фиктивную вершину <tex>s</tex>\delta(iв граф,а также ребра <tex> s \;j)to u </tex> - минимальное расстояние между вершинами весом <tex>i,\; j0 </tex> графа для всех <tex>Gu </tex>.

:Обозначим <tex>\phidelta(u,v) = \delta(s</tex> как минимальное расстояние между вершинами <tex>u,\;u)v</tex>.

:Введем потенциальную функцию <tex>w_\phi(uv) = </tex> следующим образом: <tex>\phi(u) + w(uv) - \phi(v) = \delta(s,\;u) + w(uv) - \delta(s,\;v)</tex>.

:Рассмотрим вес произвольного ребра <tex>uv \in E </tex>: <tex>\omega_\phi(uv) = \phi(u) + \omega(uv) - \phi(v) = \delta(s,\;u) + w\omega(uv) = </tex> {какой-то путь <tex>\delta(s \rightsquigarrow , v)</tex>}.

:Поскольку <tex>\delta(s,u) + \omega(uv) </tex> {{---}} вес какого-то пути <tex> s \rightsquigarrow v </tex>, а <tex> \;delta(s, v) =</tex> {минимальный путь {---}} вес кратчайшего пути <tex>s \rightsquigarrow v</tex>}, то <tex> \delta(s, u) + \omega(uv) \ge \delta(s, v) \Rightarrow \delta(s, u) + w\omega(uv) - \delta(s, v) = \omega_\varphi(uv) \ge 0 </tex>.

'''do''' <tex>w_\omega_\varphi(u,\;v) \leftarrow w\omega(u,\;v) + \varphi(u) - \varphi(v)</tex>

<tex>(G,\;w_\omega_\varphi,\;u)</tex> величин <tex>\delta_\varphi(u,\;v)</tex>