40
правок
Изменения
Нет описания правки
'''Алгоритм Джонсона''' находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа с положительными или отрицательными ребрами. Данный алгоритм работает правильно, если в графе отсутствуют отрицательные циклыно не имеющем отрицательных циклов.
== Алгоритм ==
=== Описание ===
Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин в течение времени <tex> O(V^2 * \log(V) + VE) </tex>. Для разреженных графов этот алгоритм ведет себя асиптотически быстрее алгоритма Флойда. Этот алгоритм либо возвращает матрицу кратчайших расстояний между всеми парами вершин, либо сообщение о том, что в графе существует цикл отрицательной длины.
В этом алгоритме используется метод '''изменения веса''' (англ. reweighting). Суть его заключается в том, что для заданного графа <tex> G </tex> строится новая весовая функция <tex> \hat{\omega} </tex>, неотрицательная для всех ребер графа <tex> G </tex> и сохраняющая кратчайшие пути. Такая весовая функция строится при помощи так называемой '''потенциальной''' функции.
{{Определение
|definition=
Пусть <tex> \varphi : V \rightarrow \mathbb R </tex> - произвольное отображение из множества вершин в вещественные числа. Тогда новой весовой функцией будет <tex> \hat{\omega}(u, v) = \omega(u, v) + \varphi(u) - \varphi(v) </tex>.
}}
Такая потенциальная функция строится при помощи добавлении фиктивной вершины в <tex> G </tex> и запуском алгоритма Форда-Беллмана из нее. На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графе.
Теперь, когда мы знаем, что веса всех ребер неотрицательны, и кратчайшие пути сохранятся, можно запустить алгоритм Дейкстры из каждой вершины и таким образом найти кратчайшие расстояния между всеми парами вершин.
=== Сохранение кратчайших путей ===
{{Лемма
|statement=
Пусть <tex>P,\; Q : a \rightsquigarrow b\;</tex> и <tex>w(P) < w(Q).</tex> Тогда <tex>\forall \phivarphi: \; w_\phivarphi(P) < w_\phivarphi(Q)</tex>
|proof=
:<tex>P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k </tex>
:<tex>w_\phivarphi(P) = w_\phivarphi(u_0u_1) + w_\phivarphi(u_1u_2) + ... + w_\phivarphi(u_{k-1}u_k) = \phivarphi(u_0) + w(u_0u_1) - \phivarphi(u_1) + ... + \phivarphi(u_{k-1}) + w(u_{k-1}u_k) - \phivarphi(u_k) = \phivarphi(u_0) + w(P) - \phivarphi(u_k)</tex>
:<tex>w(P) < w(Q)</tex>
:<tex>w_\phivarphi(P) = \phivarphi(a) + w(P) - \phivarphi(b)</tex>
:<tex>w_\phivarphi(Q) = \phivarphi(a) + w(Q) - \phivarphi(b)</tex>
:Отсюда, <tex>w_\phivarphi(P) < w_\phivarphi(Q)</tex>
}}
{{Теорема
|statement=
В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; w_\phivarphi(uv) \ge 0 </tex>
|proof=
<tex>\Leftarrow) </tex> : <tex>C</tex> - цикл в графе <tex>G</tex>
:<tex>w(C) = \phivarphi(u_1) + w(C) - \phivarphi(u_1) = w_\phivarphi(C) \ge 0</tex>
<tex>\Rightarrow) </tex> : Добавим вершину <tex>s</tex> в граф, соединим её со всеми вершинами графа <tex>G</tex> ребрами весом <tex>w = 0</tex>.
:''Обозначение'' : <tex>\delta(i,\;j)</tex> - минимальное расстояние между вершинами <tex>i,\; j</tex> графа <tex>G.</tex>.
:<tex>\phi(u) = \delta(s,\;u)</tex>
=== Псевдокод ===
Алгоритм Джонсона
'''then''' out << «Входной граф содержит цикл с отрицательным весом»
'''else''' '''for''' для каждой <tex>v \in V'</tex>
'''do''' присвоить величине <tex>\phivarphi(v)</tex> значение <tex>\delta(s,\;v)</tex>,
вычисленное алгоритмом Беллмана — Форда
'''for''' для каждого ребра <tex>(u,\;v) \in E'</tex>
'''do''' <tex>w_\phivarphi(u,\;v) \leftarrow w(u,\;v) + \phivarphi(u) - \phivarphi(v)</tex>
'''for''' для каждой вершины <tex>u \in V</tex>
'''do''' вычисление с помощью алгоритма Дейкстры
<tex>(G,\;w_\phivarphi,\;u)</tex> величин <tex>\delta_\phivarphi(u,\;v)</tex>
для всех вершин <tex>v \in V</tex>
'''for''' для каждой вершины <tex>v \in V</tex>
'''do''' <tex>d_{uv} \leftarrow \delta_\phivarphi(u,\;v) + \phivarphi(v) - \phivarphi(u)</tex>
'''return''' D
Итого, в начале алгоритм Форда-Беллмана либо строит потенциальную функцию такую, что после перевзвешивания все веса ребер будут неотрицательны, либо выдает сообщение о том, что в графе присутствует отрицательный цикл.
Затем из каждой вершины запускается алгоритм Дейкстры для составления искомой матрицы. Так как все веса ребер теперь неотрицательны, алгоритм Дейкстры будет работать корректно. А поскольку перевзвешивание таково, что кратчайшие пути относительно обеих весовых функций совпадают, алгоритм Джонсона в итоге корректно найдет все кратчайшие пути между всеми парами вершин.
== Сложность ==
