Johnson Algorithm to find the shortest paths between all pair of vertices

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

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 Bellman-Ford algorithms as subroutines.

Floyd-Warshall 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:

Bellman-Ford 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 Bellman-Ford algorithm on G' with added new vertex as a source. Let the distance calculated by Bellman-Ford be h[0], h[1], h[2], ... h[V-1].
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
}

Bellman-Ford : 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