Johnson’s Algorithm for All-Pair Shortest Path

Johnson’s Algorithm is used to find all pair shortest path in a graph. We can use the Johnson’s Algorithm to find the shortest paths between all pairs of vertices in an edge-weighted directed graph. Johnson’s Algorithm uses both Dijkstra's Algorithm and Bellman-Ford Algorithm.

Johnson’s Algorithm can find the all pair shortest path even in the case of the negatively weighted graphs. Although we can use the Floyd Warshall's Algorithm in order to find the all pair shortest path in the graph though Johnson’s Algorithm is much more efficient in terms of time complexity than the Floyd Warshall’s Algorithm.

Scope

• In this article, we will learn about the Johnson’s Algorithm in Data Structures.
• The Johnson’s Algorithm is an efficient technique for finding the all-pair shortest path in a graph.
• We will look over the working of this algorithm and how we can implement this algorithm.
• We will also analyze the Time complexity for the Johnson’s Algorithm.
• Finally we will see some intresting real-life applications of this algorithm.

Takeaways

• Complexity of Johnson’s Algorithm
  • Time complexity – $O(V^2log V + VE)$

Introduction to Johnson’s Algorithm

Consider a situation where a Road Construction firm has been given a tender to connect multiple villages via road network in such a way that the people can reach from one village to another in minimum possible time.

We can represent the road network as a graph where the villages can be represented in form of the nodes of the graph and the road between the villages can be represented in form of edges of the graph.

Now this problem is reduced to finding the minimum distance between all pairs of nodes in a graph.

Johnson’s Algorithm is used to find all pair shortest path in the given graph G. This problem of finding the all pair shortest path can also be solved using Floyd warshall Algorithm but the Time complexity of the Floyd warshall algorithm is $O(V^3)$, which is a polynomial-time algorithm, on the other hand, the Time complexity of Johnson’s Algorithm is $O(v^2log(V + ElogV)$ which is much more efficient than the Floyd warshall Algorithm. So we can say that Johnson’s Algorithm is an Optimised Approach to find all pair shortest path in a graph.

Johnson's Algorithm uses both Dijkstra’s Algorithm and Bellman-Ford Algorithm. Johnson’s Algorithm can find the all pair shortest path even in the case of the negatively weighted graphs. It uses the Bellman-Ford algorithm in order to eliminate negative edges by using the technique of reweighting the given graph and detecting the negative cycles.

Now once we come up with this new, modified graph, then this algorithm uses Dijkstra's shortest path algorithm to calculate the shortest path between all pairs of vertices for a given graph.

The output of Johnson’s algorithm is the set of shortest paths between every pair of vertices in the original graph. The above steps are discussed in detail below.

Three Main Parts of Johnson's Algorithm

The working of Johnson's Algorithm can be easily understood by dividing the algorithm into three major parts which are as follows

• Adding a base vertex
• Reweighting the edges
• Finding all-pairs shortest path

Now we will learn about each of the three main parts of Johnson’s Algorithm in great detail. Let us understand the working of Jhonson’s Algorithm with an example.

Consider an edge-weighted directed graph $G$ having four vertices which are $a$,$b$,$c$ and $d$ as shown in the picture below. Our goal is to calculate the shortest path between every pair of vertices in the given graph $G$.

Adding a Base Vertex

To calculate the shortest path between every pair of vertices the idea is to add a base vertex (vertex $S$ in figure below) that is directly connected to every vertex. In other words, the cost to reach each vertex from the newly added base vertex $S$ is zero. Since at this stage our graph contains negative weight edges so we apply the Bellman-Ford Algorithm.

Let the modified graph with the newly added base vertex be $G$‘ which is shown in the image below. Now after applying the Bellman-Ford Algorithm for the above-modified graph $G$‘ , we get the shortest distance from the base vertex to all other vertices which is as follows.

D(S,a)=D(S,d)+D(d,a)
D(S,a)= 0 + (-3)
D(S,a)= -3

D(S,b)= D(S,a)+D(a,b) 
D(S,b) = -3 + (-5) 
D(S,b) = -8

D(S,c)= D(S,a) + D(a,b) + D(b,c) 
D(S,c)= -3 + (-5) + 6 
D(S,c)= -2

D(S,d)=0 (Direct edge between S and d).

where D(S,V) is the shortest distance from the vertex S to the vertex V.

Reweighting the Edges

Johnson's Algorithm uses the technique of reweighting of the edges.

Reweighting is a process by which edge weight is changed to satisfy following two properties.

1. For all pairs of vertices u, v in the graph, if a certain path is the shortest path between those vertices before reweighting, it must also be the shortest path between those vertices after reweighting.
2. For all edges, (u, v), in the graph, weight(u, v) must be non-negative.

Reweighting of the edges is done because of the fact that if the weight of all the edges in a given graph G are non negative, we can find the shortest paths between all pairs of vertices just by running Dijkstra's Algorithm once from each vertex which is more efficient than applying the Bellman-Ford algorithm.

Now, the new set of edges weight W which is obtained by reweighting the edges must satisfy the following essential properties.

1. For all pair of vertices u, v ∈ V, the shortest path from u to v using weight function W is also the shortest path from u to v using weight function W.
2. For all edges (u, v), the new weight W (u, v) is non negative.

Now as we already got these distances of all the vertices from the base vertex S, we remove the source vertex S and reweight the edges using the following formula.

By using the triangle inequality, we have

D(S,v) <= W(u, v) + D(S,u)

So, by using the above equation we can define our reweighting equation as follows.

W(u, v) = W(u, v) + D(S,u) - D(S,v)

where W(u,v) is the original weight of an edge between the vertices u,v and D(S,V) is the shortest distance from the vertex S to the vertex V.

Now we calculate the new weights by using the above formula.

W(u, v) = W(u, v) + D(S,u) - D(S,v)

For the edge a to b, putting u=a amd v=b in the above formula, we get

W(a, b) = W(a, b) + D(S,a) - D(S,b)
W(a, b) = -5 + (-3) - (-8)
W(a, b) = 0

For the edge b to c, putting u=b amd v=c in the above formula, we get

W(b, c) = W(b, c) + D(S,b) - D(S,c)
W(b, c) = 6  + (-8) - (-2)
W(b, c) = 0

For the edge d to c, putting u=d amd v=c in the above formula, we get

W(d, c) = W(d, c) + D(S,d) - D(S,c)
W(d, c) = 3 + 0 - (-2)
W(a, b) = 5

For the edge a to d, putting u=a amd v=d in the above formula, we get

W(a, d) = W(a, d) D(S,a) - D(S,d)
W(a, d) = 4 + (-3) -0
W(a, d) = 1

For the edge c to a, putting u=c amd v=a in the above formula, we get

W(c, a) = W(c, a) + D(S, c) - D(S,a)
W(c, a) = 2 + (-2) - (-3)
W(c, a) = 3

For the edge b to a, putting u=b amd v=a in the above formula, we get

W(b, a) = W(b, a) + D(S, b) - D(S,a)
W(b, a) = 7 + (-8) - (-3)
W(b, a) = 2

For the edge d to a, putting u=d amd v=a in the above formula, we get

W(d, a) = W(d, a) + D(S, d) - D(S,a)
W(d, a) = -3 + 0 - (-3)
W(d, a) = 0

The Picture below shows the graph with the reweighted edges.

Finding the All-pairs Shortest Path

Now after we have reweighted the weight of the edges, we have got all the edges with the non-negative weights so we can apply the Dijkstra's Algorithm to find all pair shortest path for a given graph $G$.

After getting the shortest path for each pair of vertices it becomes very important to transform these path weights back into the original path weights so that an accurate path weight is returned at the end of the algorithm. This can be done by simply reversing the reweighting process. Finally, we get the matrix that represents the shortest path from each pair of vertices.

Now, after applying Dijkstra's Algorithm on each vertex individually, we get the shortest distance between all pairs, which is as follows.

Consider a as source vertex, the shortest distance from a to all other vertices are as follows.

D(a, a) = 0

D(a, b) = W(a, b)
D(a, b) = 0

D(a, c) = W(a, b) + W(b, c)
D(a, c) = 0 + 0 = 0

D(a, d) = W(a, d)
D(a, d) = 1

Consider b as source vertex, the shortest distance from b to all other vertices are as follows.

D(b, a)= W(b, a)
D(b, a)= 2

D(b, b)= 0

D(b, c) = W(b, c)
D(b, c) = 0

D(b, d)=W(b,a) +W(a, d)
D(b, d) = 2 + 1 = 3

Consider c as source vertex, the shortest distance from c to all other vertices are as follows.

D(c, a) = W(c,a)
D(c, a) = 3

D(c, b) = W(c, a) +W(a, b)
D(c, b) = 3 + 0
D(c, b) = 3

D(c, c) = 0

D(c, d) = W(c, a) + W(a,d)
D(c, d) =  3 + 1
D(c, d) = 4

Consider d as source vertex, the shortest distance from d to all other vertices are as follows.

D(d, a) = W(d, a)
D(d, a) = 0

D(d, b) = W(d, a) + W(a, b)
D(d, b) = 0 + 0 = 0
D(d, c) = W(d, a) + W(a, b) + W(b, c)
D(d, c) = 0 + 0 + 0 = 0

D(d, d) = 0

From the above calculation, we can represent the shortest distance between all pairs shortest paths in form of a table. The table below represents the distance between every pair of vertices.

Please note that in case of directed edge-weighted graph the distance from any vertex u to vertex v and vice versa may or may not be same like distance from vertex a to vertex b is 0 unit but distance between vertex b to vertex a is $2$ units.

Reweighting Proof

Now we have reweighted the edges of the graph. So we need to prove that reweighting the graph does not actually change the overall sum of weights of the edges. In the reweighted graph, we add the same quantity $h(s)$ − $h(t)$ where $h(s)$ and $h(t)$ are the length of the shortest path from the newly added base vertex S to the vertex s and vertex $t$ respectively. in all paths between a pair s and t of nodes added to them.

Let us see how we can mathematically prove that the concept of reweighting preserves the actual overall sum of weights of the edges. Let $p$ be a path between two vertices of the graph say $(s,t)$. Its weight $W$ in the reweighted graph is given by the following expression:

The expression below is the weight of p in the original weighting.

(w(s,p₁)+h(s)-h(p₁))+(w(p₁,p₂)+h(p₁)-h(p₂))+…+(w(p_n,t)+h(p_n)-h(t))

Every +h(p_i) is cancelled by –

h(p_i) in the previous bracketed expression therefore, we are left with the following expression for W:

(w(s,p₁)+w(p₁,p₂)+…+w(p_n,t))+h(s)-h(t)

So we can clearly see that the reweighting adds the same amount to the weight of every path from vertex $s$ to vertex t, so we can say that a path is the shortest path in the original graph if and only if it remains the shortest path after reweighting of the graph.

Now once there is no existence of negative edges, we are sure to have the optimality of the paths which are found by Dijkstra's algorithm. The distances in the original graph may be calculated from the distances calculated by Dijkstra's algorithm in the reweighted graph by reversing the reweighting transformation.

Algorithm Pseudocode

• Firstly we will create a modified graph G’ in which we will add the base vertex to the original graph G.
• We will apply the Bellman-Ford ALgorithm to check whether the graph G’ contains the negative weight cycle or not.
• We can find all pair shortest path only if the graph is free from the negative weight cycle.
• Once we found that the graph is free from the negative weight cycle then we calculate the shortest path for each vertex using Bellman-Ford algorithm.
• We also reweight the edges of the graph by removing the base vertex which will also assure us that the graph will be free from any negative-weight edges.
• Now at this stage since we have reweighted the edges our graph is guaranteed to be free from negative-weight edges so we apply the Dijkstra Algorithm for each vertex in the graph in order to find the shortest distance between every pair of vertex in the graph which is our desired goal.

Below is the Pseudocode for Johnson’s Algorithm.

Johnson's_Algorithm(G):

    1. Create a graph G` from the given graph G
       such that G`.V = G.V + {s}

       where s is a newly added base vertex 
       G`.E = G.E + ((s, u) for u in G.V), 
       and weight(s, u) = 0 for u in G.V

    2. if Bellman-Ford(s) == False:
            return "The input graph contains a negative weight cycle"
        otherwise:

            for each vertex v in G`.V:
                h(v) = distance(s, v) 
                which is computed by using 
                Bellman-Ford Algorithm

            for every edge (u, v) in G`.E:
                weight`(u, v) = weight(u, v) + h(u) - h(v)

    3.  Dist = new matrix that is used to store the shortest path 
        between all pair of vertices in the graph G and 
        initilize the whole matrix to infinity

        for vertex u in G.V:
            run Dijkstra(G, weight`, u) to compute distance`(u, v) for all v in G.V

        for each vertex v in G.V:
            D_(u, v) = distance`(u, v) + h(v) - h(u)

        return Dist

Implementation of Johnson's Algorithm

• Firstly we will create a list to store the modified wights which are represented by Altered_weights in the code below.
• We will apply the Bellman-Ford algorithm to find the modified weights.
• Our modified graph which is represented by Altered_Graph in the code below would consist of Altered_weights and it will be free from negative-weight edges.
• Now at this stage since our Altered_Graph is guaranteed to be free from negative-weight edges, we apply the Dijkstra Algorithm for each vertex in the Altered_Graph in order to find the shortest distance between every pair of vertex in the graph which is our desired goal.

Below is the implementation of Johnson’s Algorithm in Python.

# Implementation of Johnson's algorithm in Python3

# Import function to initialize the dictionary
from collections import defaultdict
INT_MAX = float('Inf')

# Function that returns the vertex 
# with minimum distance 
# from the source
def Min_Distance(dist, visit):

    (minimum, Minimum_Vertex) = (INT_MAX, 0)
    for vertex in range(len(dist)):
        if minimum > dist[vertex] and visit[vertex] == False:
            (minimum, minVertex) = (dist[vertex], vertex)

    return Minimum_Vertex


# Dijkstra Algorithm for Modified
# Graph (After removing the negative weights)
def Dijkstra_Algorithm(graph, Altered_Graph, source):

    # Number of vertices in the graph
    tot_vertices = len(graph)

    # Dictionary to check if given vertex is
    # already included in the shortest path tree
    sptSet = defaultdict(lambda : False)

    # Shortest distance of all vertices from the source
    dist = [INT_MAX] * tot_vertices

    dist[source] = 0

    for count in range(tot_vertices):

        # The current vertex which is at min Distance
        # from the source and not yet included in the
        # shortest path tree
        curVertex = Min_Distance(dist, sptSet)
        sptSet[curVertex] = True

        for vertex in range(tot_vertices):
            if ((sptSet[vertex] == False) and
                (dist[vertex] > (dist[curVertex] +
                Altered_Graph[curVertex][vertex])) and
                (graph[curVertex][vertex] != 0)):

                                                    dist[vertex] = (dist[curVertex] +Altered_Graph[curVertex][vertex])

    # Print the Shortest distance from the source
    for vertex in range(tot_vertices):
        print ('Vertex ' + str(vertex) + ': ' + str(dist[vertex]))

# Function to calculate shortest distances from source
# to all other vertices using Bellman-Ford algorithm
def BellmanFord_Algorithm(edges, graph, tot_vertices):

    # Add a source s and calculate its min
    # distance from every other node
    dist = [INT_MAX] * (tot_vertices + 1)
    dist[tot_vertices] = 0

    for i in range(tot_vertices):
        edges.append([tot_vertices, i, 0])

    for i in range(tot_vertices):
        for (source, destn, weight) in edges:
            if((dist[source] != INT_MAX) and
                    (dist[source] + weight < dist[destn])):
                dist[destn] = dist[source] + weight

    # Don't send the value for the source added
    return dist[0:tot_vertices]

# Function to implement Johnson Algorithm
def JohnsonAlgorithm(graph):

    edges = []

    # Create a list of edges for Bellman-Ford Algorithm
    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]])

    # Weights used to modify the original weights
    Alter_weigts = BellmanFord_Algorithm(edges, graph, len(graph))

    Altered_Graph = [[0 for p in range(len(graph))] for q in
                    range(len(graph))]

    # Modify the weights to get rid of negative weights
    for i in range(len(graph)):
        for j in range(len(graph[i])):

            if graph[i][j] != 0:
                Altered_Graph[i][j] = (graph[i][j] +
                        Alter_weigts[i] - Alter_weigts[j]);

    print ('Modified Graph: ' + str(Altered_Graph))

    # Run Dijkstra for every vertex as source one by one
    for source in range(len(graph)):
        print ('\nShortest Distance with vertex ' +
                        str(source) + ' as the source:\n')
        Dijkstra_Algorithm(graph, Altered_Graph, source)

# Driver Code
graph = [[0, -5, 2, 3],
        [0, 0, 4, 0],
        [0, 0, 0, 1],
        [0, 0, 0, 0]]

JohnsonAlgorithm(graph)

Output of Above Program

Modified Graph: [[0, 0, 3, 3], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Shortest Distance with vertex 0 as the source:

Vertex 0: 0
Vertex 1: 0
Vertex 2: 0
Vertex 3: 0

Shortest Distance with vertex 1 as the source:

Vertex 0: inf
Vertex 1: 0
Vertex 2: 0
Vertex 3: 0

Shortest Distance with vertex 2 as the source:

Vertex 0: inf
Vertex 1: inf
Vertex 2: 0
Vertex 3: 0

Shortest Distance with vertex 3 as the source:

Vertex 0: inf
Vertex 1: inf
Vertex 2: inf
Vertex 3: 0

Time Complexity of Johnson’s Algorithm

Since the main steps required in Johnson's Algorithm are:

1. Bellman-Ford Algorithm which is called once.
2. Dijkstra Algorithm which is called V times,
   where V is the number of vertices in the given graph G.

We know that the Time complexity of:

• Bellman Ford Algorithm is $O(VE).$
• Dijkstra Algorithm is $O(VLogV)$.

So overall time complexity is $O(V^2log V + VE)$ which is average case.

It is really interesting to know that in case of the complete graph the time complexity of Johnson’s algorithm becomes the same as that of the Floyd Warshell Algorithm.

It is important to note that the Worst-case Time complexity of the Jhonson’s algorithm is $O(V^3 + V*E)$ as Dijkstra's Algorithm takes $O(V^2)$ time.

Applications of Johnson's Algorithm

There are various applications of Jhonson's Algorithm some of them are as follows.

1. The most widely used application of the Johnsons Algorithm is the Networking of Roads.
2. Used for Network Routing for choosing the optimal path for sending the data packets.
3. Also used in Driving Directions for telling the best route with the shortest path and least traffic congestion.
4. This algorthim is widely used for Logistics purpose by different firms to minimise their transportation cost.

Conclusion

• In this article, we have learned about Johnson's Algorithm.
• We have also learned about the working of Johnson's Algorithm.
• We compared Johnson's Algorithm with the Floyd Warshall Algorithm.
• We saw how Johnson's Algorithm uses Dijkstra’s Algorithm and Bellman Ford’s Algorithm to increase the efficiency of the Johnson's Algorithm over the Floyd Warshall Algorithm in terms of time complexity.
• We have learned how to implement Johnson’s algorithm.
• We also analyzed the time complexity of this algorithm.
• We saw some interesting real-life applications of this algorithm.