Johnson Algorithm

Johnson's algorithm - allows you to find the shortest paths between all pairs of vertices of a weighted directed graph . This algorithm works if the graph contains edges with positive or negative weight, but there are no cycles with negative weight. Named after , who published the algorithm in 1977.

Content

Algorithm

Dan Earl $G=(V,E)$ ${\ displaystyle G = (V, E)}$ with weight function $\omega \colon E\to R$ ${\ displaystyle \ omega \ colon E \ to R}$ . If the weights of all the edges $\omega$ ${\ displaystyle \ omega}$ in the graph non-negative, you can find the shortest paths between all pairs of vertices by running the Dijkstra algorithm once for each vertex. If the graph contains edges with negative weight, but there are no cycles with negative weight, you can calculate a new set of edges with non-negative weights, allowing you to use the previous method. New set consisting of ribs weights ${\hat {\omega }}$ ${\ displaystyle {\ hat {\ omega}}}$ must satisfy the following properties.

For all the edges $(u,\;v)$ ${\ displaystyle (u, \; v)}$ new weight ${\hat {\omega }}(u,\;v)>0$ ${\ displaystyle {\ hat {\ omega}} (u, \; v)> 0}$ .
For all pairs of vertices $u,\;v\in V$ ${\ displaystyle u, \; v \ in V}$ way $p$ ${\ displaystyle p}$ is the shortest path from the top $u$ ${\ displaystyle u}$ to the top $v$ ${\ displaystyle v}$ using weight function $\omega$ ${\ displaystyle \ omega}$ if and only if $p$ ${\ displaystyle p}$ - also the shortest path from the top $u$ ${\ displaystyle u}$ to the top $v$ ${\ displaystyle v}$ with weight function ${\hat {\omega }}$ ${\ displaystyle {\ hat {\ omega}}}$ .

Saving Shortest Paths

Lemma (Changing weights preserves the shortest paths). Let a weighted directed graph be given $G=(V,\;E)$ ${\ displaystyle G = (V, \; E)}$ with weight function $\omega \colon E\to R$ ${\ displaystyle \ omega \ colon E \ to R}$ , let it go $h\colon V\to R$ ${\ displaystyle h \ colon V \ to R}$ Is an arbitrary function that maps vertices to real numbers. For each rib $(u,\;v)\in E$ ${\ displaystyle (u, \; v) \ in E}$ define

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

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

Let be $p=\langle v_{0},\;v_{1},\;\ldots ,\;v_{k}\rangle$ ${\ displaystyle p = \ langle v_ {0}, \; v_ {1}, \; \ ldots, \; v_ {k} \ rangle}$ - arbitrary path from the top $v_{0}$ ${\ displaystyle v_ {0}}$ to the top $v_{k}$ ${\ displaystyle v_ {k}}$ . $p$ ${\ displaystyle p}$ is the shortest path with a weight function $\omega$ ${\ displaystyle \ omega}$ if and only if it is the shortest path with a weight function ${\hat {\omega }}$ ${\ displaystyle {\ hat {\ omega}}}$ , i.e. equality $\omega (p)=\delta (v_{0},\;v_{k})$ ${\ displaystyle \ omega (p) = \ delta (v_ {0}, \; v_ {k})}$ tantamount to equality ${\hat {\omega }}(p)={\hat {\delta }}(v_{0},\;v_{k})$ ${\ displaystyle {\ hat {\ omega}} (p) = {\ hat {\ delta}} (v_ {0}, \; v_ {k})}$ . Also count $G$ ${\ displaystyle G}$ contains a negative weight cycle using a weight function $\omega$ ${\ displaystyle \ omega}$ if and only if it contains a negative weight cycle using the weight function ${\hat {\omega }}$ ${\ displaystyle {\ hat {\ omega}}}$ .

Weight Change

For this graph, create a new graph $G'=(V',\;E')$ ${\ displaystyle G '= (V', \; E ')}$ where $V'=V\cup \{s\}$ ${\ displaystyle V '= V \ cup \ {s \}}$ , for some new top $s\not \in V$ ${\ displaystyle s \ not \ in V}$ , but $E'=E\cup \{(s,\;v):v\in V\}$ ${\ displaystyle E '= E \ cup \ {(s, \; v): v \ in V \}}$ .
We expand the weight function $\omega$ ${\ displaystyle \ omega}$ so that for all vertices $v\in V$ ${\ displaystyle v \ in V}$ equality was fulfilled $\omega (s,\;v)=0$ ${\ displaystyle \ omega (s, \; v) = 0}$ .
Next we define for all vertices $v\in V'$ ${\ displaystyle v \ in V '}$ value $h(v)=\delta (s,\;v)$ ${\ displaystyle h (v) = \ delta (s, \; v)}$ and new weights for all ribs ${\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v)\geqslant 0$ ${\ displaystyle {\ hat {\ omega}} (u, \; v) = \ omega (u, \; v) + h (u) -h (v) \ geqslant 0}$ .

Basic Procedure

Johnson's algorithm uses the Bellman-Ford algorithm and Dijkstra's algorithm , implemented as subroutines. The edges are stored as lists of adjacent vertices. The algorithm returns the usual matrix $D=d_{ij}$ ${\ displaystyle D = d_ {ij}}$ the size $|V|\times |V|$ ${\ displaystyle | V | \ times | V |}$ where $d_{ij}=\delta (i,\;j)$ ${\ displaystyle d_ {ij} = \ delta (i, \; j)}$ , or displays a message that the input graph contains a cycle with a negative weight.

  Johnson Algorithm
 Count is being built  $G'$ G′{\ displaystyle G '} if Bellman_Ford $(G',\;\omega ,\;s)$ (G′,ω,s){\ displaystyle (G ', \; \ omega, \; s)}  = FALSEthen print “The input graph contains a negative weight loop”elsefor for each $v\in V'$ v∈V′{\ displaystyle v \ in V '} do assign to $h(v)$ h(v){\ displaystyle h (v)}  value $\delta (s,\;v)$ δ(s,v){\ displaystyle \ delta (s, \; v)}  ,
calculated by the Bellman-Ford algorithmfor for each edge $(u,\;v)\in E'$ (u,v)∈E′{\ displaystyle (u, \; v) \ in E '} do ${\hat {\omega }}(u,\;v)\leftarrow \omega (u,\;v)+h(u)-h(v)$ ω^(u,v)←ω(u,v)+h(u)-h(v){\ displaystyle {\ hat {\ omega}} (u, \; v) \ leftarrow \ omega (u, \; v) + h (u) -h (v)} for for each vertex $u\in V$ u∈V{\ displaystyle u \ in V} do calculation using Dijkstra's algorithm $(G,\;{\hat {\omega }},\;u)$ (G,ω^,u){\ displaystyle (G, \; {\ hat {\ omega}}, \; u)}  quantities ${\hat {\delta }}(u,\;v)$ δ^(u,v){\ displaystyle {\ hat {\ delta}} (u, \; v)} 
for all the peaks $v\in V$ v∈V{\ displaystyle v \ in V} for for each vertex $v\in V$ v∈V{\ displaystyle v \ in V} do $d_{uv}\leftarrow {\hat {\delta }}(u,\;v)+h(v)-h(u)$ duv←δ^(u,v)+h(v)-h(u){\ displaystyle d_ {uv} \ leftarrow {\ hat {\ delta}} (u, \; v) + h (v) -h (u)} return D

Difficulty

If the Dijkstra algorithm has a non-decreasing priority queue implemented in the form of aFibonacci heap , then the Johnson algorithm time

O(V^{2}\log V+VE)

{\ displaystyle O (V ^ {2} \ log V + VE)}

. With a simpler implementation of a non-decreasing priority queue, the run time becomes equal

O(VE\log V)

{\ displaystyle O (VE \ log V)}

, but for sparse graphs this quantity in the asymptotic limit behaves better than the operating time of the Floyd - Warshell algorithm .

Links

Algorithm Visualizer

Literature

Thomas H. Cormen et al. Algorithms: construction and analysis. - 2nd ed. - M .: Williams Publishing House , 2007. - S. 726. - ISBN 5-8459-0857-4 .
Thomas H. Cormen et al. Algorithms: construction and analysis. - 1st ed. - M .: MCLMO , 2004 .-- S. 523. - ISBN 5-900916-37-5 .