Johnson Algorithm to find the shortest paths between all pair of vertices
Get this book > Problems on Array: For Interviews and Competitive Programming
Reading time: 40 minutes
Johnson Algorithm is used to find shortest paths between every pair of vertices in a given weighted directed graph and here weights may be negative. Johnson Algorithm uses both Dijkstra and BellmanFord algorithms as subroutines.
FloydWarshall is most effective for dense graphs, while Johnson algorithm is most effective for sparse graphs. The reason that Johnson's algorithm is better for sparse graphs is that its time complexity depends on the number of edges in the graph.
Basically Johnson Algorithm uses:
 BellmanFord Algorithm in order to reweight the input graph for elimintaing negative edges and detect negative cycles.
 And then with modified graph, it uses Dijkstra's Algorithm to calculate shortest path between all pair of vertices.
Graph G is taken as input. Graph has a set of vertices V which maps to set of Edges E. Each edge, has their respective weights. This algorithm works on directed, weighted graphs.
Algorithm Steps

A new vertex is added to the graph G, and is connected by edges of zero weight to all other vertices in the graph. Let this modified graph be G'.

Run BellmanFord algorithm on G' with added new vertex as a source. Let the distance calculated by BellmanFord be h[0], h[1], h[2], ... h[V1].

All edges go through a reweighting process that eliminates negative weight edges. New weight assigned is original weight + h[u]  h[v].

The added vertex is removed and Dijkstra's algorithm is applied on every node in the graph.
Pseudocode
Pseudocode for Johnson Algorithm:
Input : Graph G
Output : List of all pair shortest paths for G
Johnson(G){
G'.V = G.V + {n}
G'.E = G.E + ((s,u) for u in G.V)
weight(n,u) = 0 in G.V
Dist = BellmanFord(G'.V,G'.E)
for edge(u,v) in G'.E do
weight(u,v) += h[u]  h[v]
end
L = [] /*for storing result*/
for vertex v in G.V do
L += Dijkstra(G, G.V)
end
return L
}
BellmanFord : It is used to reweight the input graph to eliminate negative edges and detect negative cycles.
More information can be found here.
Dijkstra's Algorithm : It is an algorithm for finding the shortest paths between nodes in a graph.
More information can be found here.
Implementation
Implementation of Johnson's algorithm in Python:
MAX_INT = float('Inf')
def minDistance(dist, visited):
(minimum, minVertex) = (MAX_INT, 0)
for vertex in range(len(dist)):
if minimum > dist[vertex] and visited[vertex] == False:
(minimum, minVertex) = (dist[vertex], vertex)
return minVertex
def Dijkstra(graph, modifiedGraph, src):
num_vertices = len(graph)
sptSet = defaultdict(lambda : False)
dist = [MAX_INT] * num_vertices
dist[src] = 0
for count in range(num_vertices):
curVertex = minDistance(dist, sptSet)
sptSet[curVertex] = True
for vertex in range(num_vertices):
if ((sptSet[vertex] == False) and
(dist[vertex] > (dist[curVertex] +
modifiedGraph[curVertex][vertex])) and
(graph[curVertex][vertex] != 0)):
dist[vertex] = (dist[curVertex] +
modifiedGraph[curVertex][vertex]);
for vertex in range(num_vertices):
print ('Vertex ' + str(vertex) + ': ' + str(dist[vertex]))
def BellmanFord(edges, graph, num_vertices):
dist = [MAX_INT] * (num_vertices + 1)
dist[num_vertices] = 0
for i in range(num_vertices):
edges.append([num_vertices, i, 0])
for i in range(num_vertices):
for (src, des, weight) in edges:
if((dist[src] != MAX_INT) and
(dist[src] + weight < dist[des])):
dist[des] = dist[src] + weight
return dist[0:num_vertices]
def JohnsonAlgorithm(graph):
edges = []
for i in range(len(graph)):
for j in range(len(graph[i])):
if graph[i][j] != 0:
edges.append([i, j, graph[i][j]])
modifyWeights = BellmanFord(edges, graph, len(graph))
modifiedGraph = [[0 for x in range(len(graph))] for y in
range(len(graph))]
for i in range(len(graph)):
for j in range(len(graph[i])):
if graph[i][j] != 0:
modifiedGraph[i][j] = (graph[i][j] +
modifyWeights[i]  modifyWeights[j]);
print ('Modified Graph: ' + str(modifiedGraph))
for src in range(len(graph)):
print ('\nShortest Distance with vertex ' +
str(src) + ' as the source:\n')
Dijkstra(graph, modifiedGraph, src)
graph = [[0, 8, 2, 4],
[0, 0, 2, 6],
[0, 0, 0, 2],
[0, 0, 0, 0]]
JohnsonAlgorithm(graph)
Complexity
The main steps in algorithm are:
 Bellman Ford Algorithm called once
 Dijkstra called V times.
Time complexity of:
 Bellman Ford is O(VE)
 Dijkstra is O(VLogV).
So overall time complexity is O(V^(2)*log V + VE).
The time complexity of Johnson's algorithm becomes same as Floyd Warshell when the graphs is complete.
Worst Time complexity of above algorithm is O(V^(3) + V*E) as Dijkstra's Algorithm takes O(n^(2)).
Applications
 Johnson's algorithm is a shortest path algorithm that deals with the all pairs shortest path problem.
 It is used in case of Sparse graphs (graphs with a few edges)
References
 Introduction to Algorithms 3rd Edition by Clifford Stein, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest