Johnson’s algorithm for All-pairs shortest paths
• Johnson's Algorithm uses both Dijkstra's Algorithm and
Bellman-Ford Algorithm.
• Johnson's Algorithm uses the technique of "reweighting."
• If all edge weights w in a graph G = (V, E) are
nonnegative, we can find the shortest paths between all
pairs of vertices by running Dijkstra's Algorithm once from
each vertex.
• If G has negative - weight edges, we compute a new - set
of non - negative edge weights that allows us to use the
same method.
The new set of edges weight must satisfy two essential
properties:
• For each edge (u, v) ∈ E define
• Where h (u) = label of u
h (v) = label of v
Step1: Take any source vertex's' outside the graph and make distance from 's' to every
vertex '0'.
Step2: Apply Bellman-Ford Algorithm and calculate minimum weight on each vertex.
Dist s a b c d
K=1 0 0 0 0 0
K=2 0 -1 -3 0 0
K=3 0 -1 -4 0 0
K=4 0 -1 -4 -1 0
h(a)=-1
h(b)=-4
h(c)=-1
h(d)=0
s
Step3: w (a, b) = w (a, b) + h (a) - h (b)
= -3 + (-1) - (-4)
=0
w (b, a) = w (b, a) + h (b) - h (a)
= 5 + (-4) - (-1)
=2
w (b, c) = w (b, c) + h (b) - h (c)
w (b, c) = 3 + (-4) - (-1)
=0
w (c, a) = w (c, a) + h (c) - h (a)
w (c, a) = 1 + (-1) - (-1)
=1
w (d, c) = w (d, c) + h (d) - h (c)
w (d, c) = 4 + 0 - (-1)
=5
w (d, a) = w (d, a) + h (d) - h (a)
w (d, a) = -1 + 0 - (-1)
=0
w (a, d) = w (a, d) + h (a) - h (d)
w (a, d) = 2 + (-1) - 0 = 1
Reconstruct the graph with above new weights
Graph with new weights and
• Step 4: Now all edge weights are positive and now we can remove s vertex
apply Dijkstra's Algorithm on each vertex and make a matrix
ie δ (u, v) corresponds to each vertex in a graph.
• First consider ‘a’ as source and find shortest distance to all
other vertices.
• The shortest distance from ‘a’ to all other vertices is
a b c d
0 0 0 1
• This will become the first row in δ (u, v)
matrix
• Make ‘b’ as source and find shortest paths to all other
vertices. This will be the second row in the table
a b c d
1 0 0 2
• Similarly make ‘c’ and ‘d’ a source , find shortest paths
• Step 4: Final δ (u, v) matrix after applying Dijkstra's Algorithm on each vertex is given
below
δ (u, v)
• In the next step using this table re- calculation of weights has to be done
using duv ← δ (u, v) + h (v) - h (u)
‘h’ values need to be taken from step-2
duv ← δ (u, v) + h (v) - h (u)
d (a, a) = 0 + (-1) - (-1) = 0
d (a, b) = 0 + (-4) - (-1) = -3
d (a, c) = 0 + (-1) - (-1) = 0
d (a, d) = 1 + (0) - (-1) = 2
d (b, a) = 1 + (-1) - (-4) = 4
d (b, b) = 0 + (-4) - (-4) = 0
d (b,c) = 0+(-1)+4=3
d (c, a) = 1 + (-1) - (-1) = 1
d (c, b) = 1 + (-4) - (-1) = -2
d (c, c) = 0
d (c, d) = 2 + (0) - (-1) = 3
d (d, a) = 0 + (-1) - (0) = -1
d (d, b) = 0 + (-4) - (0) = -4
d (d, c) = 0 + (-1) - (0) = -1
d (d, d) = 0
Final Result shortest distance from all vertices to each other
Algorithm
