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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сохранение кратчайших путей)
(Изменение веса)
Строка 22: Строка 22:
 
}}
 
}}
  
=== Изменение веса ===
+
=== Теорема о существовании потенциальной функции ===
 +
{{Теорема
 +
|statement=
 +
В графе <tex>G</tex> нет отрицательных циклов тогда и только тогда, когда существует потенциальная функция <tex> \phi:\; \forall u,v\; w_\phi(uv) >= 0 </tex>
 +
|proof=
 +
<tex>\Leftarrow) </tex>
 +
<tex>w(C) = \phi(u_1) + w(c) - \phi(u_1) = w_\phi(C) >= 0</tex>
 +
 
 +
<tex>\Rightarrow) </tex> Добавим вершину <tex>s</tex> в граф, соединим её со всеми вершинами графа <tex>G</tex> ребрами весом <tex>w = 0</tex>.
 +
<tex>\phi(u) = \delta(s,\;u)</tex>
 +
 
 +
<tex>w_\phi(uv) = \phi(u) + w(uv) - \phi(v) = \delta(s,\;u) + w(uv) - \delta(s,\;v)</tex>.
 +
 
 +
<tex>\delta(s,\;u) + w(uv) = </tex> {какой-то путь <tex>s \rightsquigarrow v</tex>}.
 +
 
 +
<tex>\delta(s,\;v) =</tex> {минимальный путь <tex>s \rightsquigarrow v</tex>}.
 +
 
 +
Следовательно, <tex>w_\phi(uv) >= 0</tex>
 +
}}
  
 
=== Псевдокод ===
 
=== Псевдокод ===

Версия 05:49, 19 ноября 2010

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

Алгоритм

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

Пусть есть потенциальная функция: [math]\phi: V \rightarrow \mathbb{R}, \; uv [/math] - ребро, тогда [math] w_\phi(uv) = w(uv) + \phi(u) - \phi(v) [/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: \;\rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k [/math]

[math]w_\phi(P) = w_\phi(u_1u_2) + w_\phi(u_2u_3) + ... + w_\phi(u_{k-1}u_k) = \phi(u_1) + w(u_1u_2) - \phi(u_2) + ... - \phi(u_{k-1})+\phi(u_{k-1}) + w(u_{k-1}u_k) - \phi(u_k) = \phi(u_1) + 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]

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

Теорема:
В графе [math]G[/math] нет отрицательных циклов тогда и только тогда, когда существует потенциальная функция [math] \phi:\; \forall u,v\; w_\phi(uv) \gt = 0 [/math]
Доказательство:
[math]\triangleright[/math]

[math]\Leftarrow) [/math] [math]w(C) = \phi(u_1) + w(c) - \phi(u_1) = w_\phi(C) \gt = 0[/math]

[math]\Rightarrow) [/math] Добавим вершину [math]s[/math] в граф, соединим её со всеми вершинами графа [math]G[/math] ребрами весом [math]w = 0[/math]. [math]\phi(u) = \delta(s,\;u)[/math]

[math]w_\phi(uv) = \phi(u) + w(uv) - \phi(v) = \delta(s,\;u) + w(uv) - \delta(s,\;v)[/math].

[math]\delta(s,\;u) + w(uv) = [/math] {какой-то путь [math]s \rightsquigarrow v[/math]}.

[math]\delta(s,\;v) =[/math] {минимальный путь [math]s \rightsquigarrow v[/math]}.

Следовательно, [math]w_\phi(uv) \gt = 0[/math]
[math]\triangleleft[/math]

Псевдокод

В алгоритме Джонсона используется алгоритм Беллмана — Форда и алгоритм Дейкстры. Алгоритм возврашает обычную матрицу [math]D = d_{ij}[/math] размером [math]|V|\times |V|[/math], где [math]d_{ij} = \delta(i,\;j)[/math], или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.

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

Строится граф [math]G'[/math]
if Bellman_Ford[math](G',\;\omega,\;s)[/math] == FALSE
   then out << «Входной граф содержит цикл с отрицательным весом»
   else for для каждой [math]v \in V'[/math]
        do присвоить величине [math]h(v)[/math] значение [math]\delta(s,\;v)[/math],
           вычисленное алгоритмом Беллмана — Форда
        for для каждого ребра [math](u,\;v) \in E'[/math]
            do [math]\hat{\omega}(u,\;v) \leftarrow \omega(u,\;v) + h(u) - h(v)[/math]
        for для каждой вершины [math]u \in V[/math]
            do вычисление с помощью алгоритма Дейкстры
            [math](G,\;\hat{\omega},\;u)[/math] величин [math]\hat{\delta}(u,\;v)[/math]
            для всех вершин [math]v \in V[/math]
            for для каждой вершины [math]v \in V[/math]
                do [math]d_{uv} \leftarrow \hat{\delta}(u,\;v) + h(v) - h(u)[/math]
   return D

Сложность

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

См. также

Литература

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