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

Лема (Зміна ваг зберігає найкоротші шляхи). Нехай дано зважений орієнтований граф ${\displaystyle G=(V,\;E)}$ з ваговою функцією ${\displaystyle \omega :E\to R}$, і нехай ${\displaystyle h:V\to R}$ — довільна функція, що відображує вершини на дійсні числа. Для кожного ребра ${\displaystyle (u,\;v)\in E}$ визначмо

${\displaystyle {\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v).}$

Нехай ${\displaystyle p=\langle v_{0},\;v_{1},\;\ldots ,\;v_{k}\rangle }$ є довільним шляхом з вершини ${\displaystyle v_{0}}$ до вершини ${\displaystyle v_{k}}$. ${\displaystyle p}$ є найкоротшим шляхом з ваговою функцією ${\displaystyle \omega }$ тоді й лише тоді, коли він є найкоротшим шляхом з ваговою функцією ${\displaystyle {\hat {\omega }}}$, тобто рівність ${\displaystyle \omega (p)=\delta (v_{0},\;v_{k})}$ є рівносильною рівності ${\displaystyle {\hat {\omega }}(p)={\hat {\delta }}(v_{0},\;v_{k})}$. Крім того, граф ${\displaystyle G}$ містить цикл з від'ємною вагою з використанням вагової функції ${\displaystyle \omega }$ тоді й лише тоді, коли він містить цикл з від'ємною вагою з використанням вагової функції ${\displaystyle {\hat {\omega }}}$.

1. Для даного графу створімо новий граф ${\displaystyle G'=(V',\;E')}$, де ${\displaystyle V'=V\cup \{s\}}$, для деякої нової вершини ${\displaystyle s\not \in V}$, а ${\displaystyle E'=E\cup \{(s,\;v):v\in V\}}$.
2. Розширмо вагову функцію ${\displaystyle \omega }$ таким чином, щоби для всіх вершин ${\displaystyle v\in V}$ зберігалася рівність ${\displaystyle \omega (s,\;v)=0}$.
3. Далі визначмо для всіх вершин ${\displaystyle v\in V'}$ величину ${\displaystyle h(v)=\delta (s,\;v)}$ та нові ваги для всіх ребер ${\displaystyle {\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v)\geqslant 0}$.

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

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

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