Алгоритм Джонсона — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(не показано 45 промежуточных версий 9 участников)
Строка 1: Строка 1:
'''Алгоритм Джонсона''' находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа с положительными или отрицательными ребрами. Данный алгоритм работает правильно, если в графе отсутствуют отрицательные циклы.
+
'''Алгоритм Джонсона''' (англ. ''Johnson's algorithm'') находит кратчайшие пути между всеми парами вершин во взвешенном ориентированном графе с любыми весами ребер, но не имеющем отрицательных циклов.
  
 
== Алгоритм ==
 
== Алгоритм ==
 +
 +
=== Описание ===
 +
 +
Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин в течение времени <tex> O(V^2\log(V) + VE) </tex>. Для разреженных графов этот алгоритм ведет себя асимптотически быстрее [[Алгоритм Флойда|алгоритма Флойда]]. Этот алгоритм либо возвращает матрицу кратчайших расстояний между всеми парами вершин, либо сообщение о том, что в графе существует цикл отрицательной длины.
 +
 +
В этом алгоритме используется метод '''изменения веса''' (англ. ''reweighting''). Суть его заключается в том, что для заданного графа <tex> G </tex> строится новая весовая функция <tex> \omega_\varphi </tex>, неотрицательная для всех ребер графа <tex> G </tex> и сохраняющая кратчайшие пути. Такая весовая функция строится с помощью так называемой [[Амортизационный_анализ#.D0.9C.D0.B5.D1.82.D0.BE.D0.B4_.D0.BF.D0.BE.D1.82.D0.B5.D0.BD.D1.86.D0.B8.D0.B0.D0.BB.D0.BE.D0.B2|потенциальной]] функции.
 +
 +
Пусть <tex> \varphi : V \rightarrow \mathbb R </tex> — произвольное отображение из множества вершин в вещественные числа. Тогда новой весовой функцией будет <tex> \omega_\varphi(u, v) = \omega(u, v) + \varphi(u) - \varphi(v) </tex>.
 +
 +
Такая потенциальная функция строится добавлем фиктивной вершины <tex> s </tex> в <tex> G </tex>, из которой проведены ориентированные ребра нулевого веса во все остальные вершины графа, и запуском [[Алгоритм Форда-Беллмана|алгоритма Форда-Беллмана]] из нее (<tex> \varphi(v) </tex> будет равно длине кратчайшего пути из <tex> s </tex> в  <tex> v </tex>). На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графе.
 +
 +
Теперь, когда мы знаем, что веса всех ребер неотрицательны, и кратчайшие пути сохранятся, можно запустить [[Алгоритм Дейкстры|алгоритм Дейкстры]] из каждой вершины и таким образом найти кратчайшие расстояния между всеми парами вершин.
  
 
=== Сохранение кратчайших путей ===
 
=== Сохранение кратчайших путей ===
 +
Утверждается, что если какой-то путь <tex> P </tex> был кратчайшим относительно весовой функции <tex> \omega </tex>, то он будет кратчайшим и относительно новой весовой функции <tex> \omega_\varphi </tex>.
 +
 +
{{Лемма
 +
|statement=
 +
Пусть <tex>P,\; Q </tex> {{---}} два пути <tex> a \rightsquigarrow b\;</tex> и <tex>\omega(P) < \omega(Q).</tex> Тогда <tex>\forall \varphi: \; \omega_\varphi(P) < \omega_\varphi(Q)</tex>
 +
|proof=
 +
 +
:Рассмотрим путь <tex>P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_k </tex>
 +
 +
:Его вес с новой весовой функцией равен <tex>\omega_\varphi(P) = \omega_\varphi(u_0u_1) + \omega_\varphi(u_1u_2) + \ldots + \omega_\varphi(u_{k-1}u_k) </tex>.
 +
 +
:Вставим определение функции <tex> \omega_\varphi : \omega_\varphi(P) = \varphi(u_0) + \omega(u_0u_1) - \varphi(u_1) + \ldots + \varphi(u_{k-1}) + \omega(u_{k-1}u_k) - \varphi(u_k) </tex>
  
=== Изменение веса ===
+
:Заметим, что потенциалы все промежуточных вершин в пути сократятся. <tex> \omega_\varphi(P) = \varphi(u_0) + \omega(P) - \varphi(u_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>\omega_\varphi(P) < \omega_\varphi(Q)</tex>
 +
}}
 +
 
 +
=== Теорема о существовании потенциальной функции ===
 +
{{Теорема
 +
|statement=
 +
 
 +
В графе <tex>G</tex> нет отрицательных циклов <tex>\Leftrightarrow</tex> существует потенциальная функция <tex> \phi:\; \forall uv \in E\; \omega_\varphi(uv) \geqslant 0 </tex>
 +
 
 +
|proof=
 +
 
 +
<tex>\Leftarrow </tex>: Рассмотрим произвольный <tex>C</tex> — цикл в графе <tex>G</tex>
 +
 
 +
:По лемме, его вес равен <tex> \omega(C) = \omega_\varphi(C) + \varphi(u_0) - \varphi(u_0) = \omega_\varphi(C) \geqslant 0</tex>
 +
 
 +
<tex>\Rightarrow </tex>: Добавим фиктивную вершину <tex>s</tex> в граф, а также ребра <tex> s \to u </tex> весом <tex> 0 </tex> для всех <tex> u </tex>.
 +
 
 +
:Обозначим <tex>\delta(u,v)</tex> как минимальное расстояние между вершинами <tex>u,\; v</tex>, введем потенциальную функцию <tex> \phi </tex>
 +
 
 +
: <tex>\phi(u) = \delta(s,u)</tex>
 +
 
 +
:Рассмотрим вес произвольного ребра <tex> uv \in E </tex>: <tex>\omega_\phi(uv) = \phi(u) + \omega(uv) - \phi(v) = \delta(s, u) + \omega(uv) - \delta(s, 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) \geqslant \delta(s, v) \Rightarrow \delta(s, u) + \omega(uv) - \delta(s, v) = \omega_\varphi(uv) \geqslant 0 </tex>.
 +
 
 +
}}
  
 
=== Псевдокод ===
 
=== Псевдокод ===
В алгоритме Джонсона используется [[алгоритм Беллмана — Форда]] и [[алгоритм Дейкстры]]. Алгоритм возврашает обычную матрицу <tex>D = d_{ij}</tex> размером <tex>|V|\times |V|</tex>, где <tex>d_{ij} = \delta(i,\;j)</tex>, или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.
 
  
Алгоритм Джонсона
+
Предварительно построим граф  <tex>G' = (V',\;E')</tex>, где <tex>V' = V \cup \{s\}</tex>,  <tex>s \not\in V</tex>, а <tex>E' = E \cup \{(s,\;v): \omega(s, v) = 0,\ v \in V \}</tex>
 +
'''function''' Johnson(G): '''int[][]'''
 +
    '''if''' BellmanFord<tex>(G',\;\omega,\;s)</tex> == ''false''
 +
        print "Входной граф содержит цикл с отрицательным весом"
 +
        '''return''' <tex>\varnothing</tex>
 +
    '''else''' '''for''' <tex>v \in V'</tex>
 +
        <tex>\varphi(v)</tex> = <tex>\delta(s,\;v)</tex> <font color = green>// <tex>\delta(s,\;v)</tex> вычислено алгоритмом Беллмана — Форда</font>
 +
        '''for''' <tex>(u,\;v) \in E'</tex>
 +
            <tex>\omega_\varphi(u,\;v)</tex> = <tex> \omega(u,\;v) + \varphi(u) - \varphi(v)</tex>
 +
        '''for''' <tex>u \in V</tex>
 +
            Dijkstra<tex>(G,\;\omega_\varphi,\;u)</tex>
 +
            '''for''' <tex>v \in V</tex>
 +
                <tex>d_{uv} \leftarrow \delta_\varphi(u,\;v) + \varphi(v) - \varphi(u)</tex>
 +
        '''return''' <tex>d</tex>
  
Строится граф <tex>G'</tex>
+
Итого, в начале алгоритм Форда-Беллмана либо строит потенциальную функцию такую, что после перевзвешивания все веса ребер будут неотрицательны, либо выдает сообщение о том, что в графе присутствует отрицательный цикл.
'''if''' Bellman_Ford<tex>(G',\;\omega,\;s)</tex> == FALSE
+
 
    '''then''' out << «Входной граф содержит цикл с отрицательным весом»
+
Затем из каждой вершины запускается алгоритм Дейкстры для составления искомой матрицы. Так как все веса ребер теперь неотрицательны, алгоритм Дейкстры будет работать корректно. А поскольку перевзвешивание таково, что кратчайшие пути относительно обеих весовых функций совпадают, алгоритм Джонсона в итоге корректно найдет все кратчайшие пути между всеми парами вершин.
    '''else''' '''for''' для каждой <tex>v \in V'</tex>
 
        '''do''' присвоить величине <tex>h(v)</tex> значение <tex>\delta(s,\;v)</tex>,
 
            вычисленное алгоритмом Беллмана — Форда
 
        '''for''' для каждого ребра <tex>(u,\;v) \in E'</tex>
 
            '''do''' <tex>\hat{\omega}(u,\;v) \leftarrow \omega(u,\;v) + h(u) - h(v)</tex>
 
        '''for''' для каждой вершины <tex>u \in V</tex>
 
            '''do''' вычисление с помощью алгоритма Дейкстры
 
            <tex>(G,\;\hat{\omega},\;u)</tex> величин <tex>\hat{\delta}(u,\;v)</tex>
 
            для всех вершин <tex>v \in V</tex>
 
            '''for''' для каждой вершины <tex>v \in V</tex>
 
                '''do''' <tex>d_{uv} \leftarrow \hat{\delta}(u,\;v) + h(v) - h(u)</tex>
 
    '''return''' D
 
  
 
== Сложность ==
 
== Сложность ==
Алгоритм Джонсона работает за <tex>O(VE + VD)</tex>, где <tex>O(D)</tex> - время работы [[Алгоритм Дейктсры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B1%D0%BE%D0%BD%D0%B0%D1%87%D1%87%D0%B8%D0%B5%D0%B2%D0%B0_%D0%BA%D1%83%D1%87%D0%B0 фибоначчиевой кучи], то время работы алгоритма Джонсона равно <tex>O(V^2\log V + V E)</tex>.
+
Алгоритм Джонсона работает за <tex>O(VE + VD)</tex>, где <tex>O(D)</tex> время работы [[Алгоритм Дейкстры| алгоритма Дейкстры]]. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде [[Фибоначчиевы кучи| фибоначчиевой кучи]], то время работы алгоритма Джонсона есть <tex>O(V^2\log V + V E)</tex>. В случае реализации очереди с приоритетами в виде двоичной кучи время работы равно <tex>O(V E \log V)</tex>.
  
 
== См. также ==
 
== См. также ==
 
* [[Алгоритм Дейкстры]]
 
* [[Алгоритм Дейкстры]]
* [[Алгоритм Беллмана — Форда]]
+
* [[Алгоритм Форда-Беллмана]]
* [[Алгоритм Флойда — Уоршелла]]
+
* [[Алгоритм Флойда]]
 +
 
 +
== Источники информации ==
 +
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ. 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
 
* [http://rain.ifmo.ru/cat/view.php/vis/graph-paths/johnson-2001 Визуализатор алгоритма]
 
* [http://rain.ifmo.ru/cat/view.php/vis/graph-paths/johnson-2001 Визуализатор алгоритма]
  
== Литература ==
+
[[Категория: Алгоритмы и структуры данных]]
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
+
[[Категория: Кратчайшие пути в графах ]]

Версия 22:48, 13 сентября 2016

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

Алгоритм

Описание

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

В этом алгоритме используется метод изменения веса (англ. reweighting). Суть его заключается в том, что для заданного графа [math] G [/math] строится новая весовая функция [math] \omega_\varphi [/math], неотрицательная для всех ребер графа [math] G [/math] и сохраняющая кратчайшие пути. Такая весовая функция строится с помощью так называемой потенциальной функции.

Пусть [math] \varphi : V \rightarrow \mathbb R [/math] — произвольное отображение из множества вершин в вещественные числа. Тогда новой весовой функцией будет [math] \omega_\varphi(u, v) = \omega(u, v) + \varphi(u) - \varphi(v) [/math].

Такая потенциальная функция строится добавлем фиктивной вершины [math] s [/math] в [math] G [/math], из которой проведены ориентированные ребра нулевого веса во все остальные вершины графа, и запуском алгоритма Форда-Беллмана из нее ([math] \varphi(v) [/math] будет равно длине кратчайшего пути из [math] s [/math] в [math] v [/math]). На этом же этапе мы сможем обнаружить наличие отрицательного цикла в графе.

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

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

Утверждается, что если какой-то путь [math] P [/math] был кратчайшим относительно весовой функции [math] \omega [/math], то он будет кратчайшим и относительно новой весовой функции [math] \omega_\varphi [/math].

Лемма:
Пусть [math]P,\; Q [/math] — два пути [math] a \rightsquigarrow b\;[/math] и [math]\omega(P) \lt \omega(Q).[/math] Тогда [math]\forall \varphi: \; \omega_\varphi(P) \lt \omega_\varphi(Q)[/math]
Доказательство:
[math]\triangleright[/math]
Рассмотрим путь [math]P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_k [/math]
Его вес с новой весовой функцией равен [math]\omega_\varphi(P) = \omega_\varphi(u_0u_1) + \omega_\varphi(u_1u_2) + \ldots + \omega_\varphi(u_{k-1}u_k) [/math].
Вставим определение функции [math] \omega_\varphi : \omega_\varphi(P) = \varphi(u_0) + \omega(u_0u_1) - \varphi(u_1) + \ldots + \varphi(u_{k-1}) + \omega(u_{k-1}u_k) - \varphi(u_k) [/math]
Заметим, что потенциалы все промежуточных вершин в пути сократятся. [math] \omega_\varphi(P) = \varphi(u_0) + \omega(P) - \varphi(u_k)[/math]
По изначальному предположению: [math]\omega(P) \lt \omega(Q)[/math]. С новой весовой функцией веса соответствующих путей будут:
[math]\omega_\varphi(P) = \varphi(a) + \omega(P) - \varphi(b)[/math]
[math]\omega_\varphi(Q) = \varphi(a) + \omega(Q) - \varphi(b)[/math]
Отсюда, [math]\omega_\varphi(P) \lt \omega_\varphi(Q)[/math]
[math]\triangleleft[/math]

Теорема о существовании потенциальной функции

Теорема:
В графе [math]G[/math] нет отрицательных циклов [math]\Leftrightarrow[/math] существует потенциальная функция [math] \phi:\; \forall uv \in E\; \omega_\varphi(uv) \geqslant 0 [/math]
Доказательство:
[math]\triangleright[/math]

[math]\Leftarrow [/math]: Рассмотрим произвольный [math]C[/math] — цикл в графе [math]G[/math]

По лемме, его вес равен [math] \omega(C) = \omega_\varphi(C) + \varphi(u_0) - \varphi(u_0) = \omega_\varphi(C) \geqslant 0[/math]

[math]\Rightarrow [/math]: Добавим фиктивную вершину [math]s[/math] в граф, а также ребра [math] s \to u [/math] весом [math] 0 [/math] для всех [math] u [/math].

Обозначим [math]\delta(u,v)[/math] как минимальное расстояние между вершинами [math]u,\; v[/math], введем потенциальную функцию [math] \phi [/math]
[math]\phi(u) = \delta(s,u)[/math]
Рассмотрим вес произвольного ребра [math] uv \in E [/math]: [math]\omega_\phi(uv) = \phi(u) + \omega(uv) - \phi(v) = \delta(s, u) + \omega(uv) - \delta(s, v)[/math].
Поскольку [math]\delta(s, u) + \omega(uv) [/math] — вес какого-то пути [math] s \rightsquigarrow v [/math], а [math] \delta(s, v) [/math] — вес кратчайшего пути [math] s \rightsquigarrow v[/math], то [math] \delta(s, u) + \omega(uv) \geqslant \delta(s, v) \Rightarrow \delta(s, u) + \omega(uv) - \delta(s, v) = \omega_\varphi(uv) \geqslant 0 [/math].
[math]\triangleleft[/math]

Псевдокод

Предварительно построим граф [math]G' = (V',\;E')[/math], где [math]V' = V \cup \{s\}[/math], [math]s \not\in V[/math], а [math]E' = E \cup \{(s,\;v): \omega(s, v) = 0,\ v \in V \}[/math]

function Johnson(G): int[][]
    if BellmanFord[math](G',\;\omega,\;s)[/math] == false
        print "Входной граф содержит цикл с отрицательным весом"
        return [math]\varnothing[/math]
    else for [math]v \in V'[/math]
        [math]\varphi(v)[/math] = [math]\delta(s,\;v)[/math] // [math]\delta(s,\;v)[/math] вычислено алгоритмом Беллмана — Форда
        for [math](u,\;v) \in E'[/math]
            [math]\omega_\varphi(u,\;v)[/math] = [math] \omega(u,\;v) + \varphi(u) - \varphi(v)[/math]
        for [math]u \in V[/math]
            Dijkstra[math](G,\;\omega_\varphi,\;u)[/math]
            for [math]v \in V[/math]
                [math]d_{uv} \leftarrow \delta_\varphi(u,\;v) + \varphi(v) - \varphi(u)[/math]
        return [math]d[/math]

Итого, в начале алгоритм Форда-Беллмана либо строит потенциальную функцию такую, что после перевзвешивания все веса ребер будут неотрицательны, либо выдает сообщение о том, что в графе присутствует отрицательный цикл.

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

Сложность

Алгоритм Джонсона работает за [math]O(VE + VD)[/math], где [math]O(D)[/math] — время работы алгоритма Дейкстры. Если в алгоритме Дейкстры неубывающая очередь с приоритетами реализована в виде фибоначчиевой кучи, то время работы алгоритма Джонсона есть [math]O(V^2\log V + V E)[/math]. В случае реализации очереди с приоритетами в виде двоичной кучи время работы равно [math]O(V E \log V)[/math].

См. также

Источники информации

  • Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
  • Визуализатор алгоритма