Johnson’s algorithm for All-pairs shortest paths

Last Updated : 10 Aug, 2023

The problem is to find the shortest paths between every pair of vertices in a given weighted directed Graph and weights may be negative. We have discussed Floyd Warshall Algorithm for this problem. The time complexity of the Floyd Warshall Algorithm is Θ(V³).

Using Johnson’s algorithm, we can find all pair shortest paths in O(V²log V + VE) time. Johnson’s algorithm uses both Dijkstra and Bellman-Ford as subroutines. If we apply Dijkstra’s Single Source shortest path algorithm for every vertex, considering every vertex as the source, we can find all pair shortest paths in O(V*VLogV) time.

So using Dijkstra’s single-source shortest path seems to be a better option than Floyd Warshall’s Algorithm(https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/?ref=lbp) , but the problem with Dijkstra’s algorithm is, that it doesn’t work for negative weight edge. The idea of Johnson’s algorithm is to re-weight all edges and make them all positive, then apply Dijkstra’s algorithm for every vertex.

How to transform a given graph into a graph with all non-negative weight edges?

One may think of a simple approach of finding the minimum weight edge and adding this weight to all edges. Unfortunately, this doesn’t work as there may be a different number of edges in different paths (See this for an example). If there are multiple paths from a vertex u to v, then all paths must be increased by the same amount, so that the shortest path remains the shortest in the transformed graph. The idea of Johnson’s algorithm is to assign a weight to every vertex. Let the weight assigned to vertex u be h[u].

We reweight edges using vertex weights. For example, for an edge (u, v) of weight w(u, v), the new weight becomes w(u, v) + h[u] – h[v]. The great thing about this reweighting is, that all set of paths between any two vertices is increased by the same amount and all negative weights become non-negative. Consider any path between two vertices s and t, the weight of every path is increased by h[s] – h[t], and all h[] values of vertices on the path from s to t cancel each other.

How do we calculate h[] values?

Bellman-Ford algorithm is used for this purpose. Following is the complete algorithm. A new vertex is added to the graph and connected to all existing vertices. The shortest distance values from the new vertex to all existing vertices are h[] values.

Algorithm:

Let the given graph be G. Add a new vertex s to the graph, add edges from the new vertex to all vertices of G. Let the modified graph be G’.

Run the Bellman-Ford algorithm on G’ with s as the source. Let the distances calculated by Bellman-Ford be h[0], h[1], .. h[V-1]. If we find a negative weight cycle, then return. Note that the negative weight cycle cannot be created by new vertex s as there is no edge to s. All edges are from s.

Reweight the edges of the original graph. For each edge (u, v), assign the new weight as “original weight + h[u] – h[v]”.

Remove the added vertex s and run Dijkstra’s algorithm for every vertex.

How does the transformation ensure nonnegative weight edges?

The following property is always true about h[] values as they are the shortest distances.

   h[v] <= h[u] + w(u, v)

The property simply means that the shortest distance from s to v must be smaller than or equal to the shortest distance from s to u plus the weight of the edge (u, v). The new weights are w(u, v) + h[u] – h[v]. The value of the new weights must be greater than or equal to zero because of the inequality “h[v] <= h[u] + w(u, v)”.

Example: Let us consider the following graph.

Johnson1

We add a source s and add edges from s to all vertices of the original graph. In the following diagram s is 4.

Johnson2

We calculate the shortest distances from 4 to all other vertices using Bellman-Ford algorithm. The shortest distances from 4 to 0, 1, 2 and 3 are 0, -5, -1 and 0 respectively, i.e., h[] = {0, -5, -1, 0}. Once we get these distances, we remove the source vertex 4 and reweight the edges using following formula. w(u, v) = w(u, v) + h[u] – h[v].

Johnson3

Since all weights are positive now, we can run Dijkstra’s shortest path algorithm for every vertex as the source.

C++

#include <bits/stdc++.h>
#define INF 99999
using namespace std;
 
// Number of vertices in the graph
#define V 4
 
// A utility function to find the vertex with minimum
// distance value, from the set of vertices not yet included
// in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
    // Initialize min value
    int min = INT_MAX, min_index;
 
    for (int v = 0; v < V; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
 
    return min_index;
}
 
// A utility function to print the constructed distance
// array
void printSolution(int dist[][V])
{
    printf("Following matrix shows the shortest distances"
           " between every pair of vertices \n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf("%7d", dist[i][j]);
        }
        printf("\n");
    }
}
 
// Solves the all-pairs shortest path problem using
// Johnson's algorithm
void floydWarshall(int graph[][V])
{
    int dist[V][V], i, j, k;
 
    /* Initialize the solution matrix same as input graph
       matrix. Or we can say the initial values of shortest
       distances are based
       on shortest paths considering no intermediate vertex.
     */
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];
 
    /* Add all vertices one by one to the set of
      intermediate vertices.
      ---> Before start of a iteration, we have shortest
      distances between all pairs of vertices such that the
      shortest distances consider only the vertices in set
      {0, 1, 2, .. k-1} as intermediate vertices.
      ----> After the end of a iteration, vertex no. k is
      added to the set of
      intermediate vertices and the set becomes {0, 1, 2, ..
      k} */
    for (k = 0; k < V; k++) {
        // Pick all vertices as source one by one
        for (i = 0; i < V; i++) {
            // Pick all vertices as destination for the
            // above picked source
            for (j = 0; j < V; j++) {
                // If vertex k is on the shortest path from
                // i to j, then update the value of
                // dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
 
    // Print the shortest distance matrix
    printSolution(dist);
}
 
// driver program to test above function
int main()
{
    /* Let us create the following weighted graph
             10
        (0)------->(3)
         |         /|\
       5 |          |
         |          | 1
        \|/         |
        (1)------->(2)
             3           */
    int graph[V][V] = { { 0, 5, INF, 10 },
                        { INF, 0, 3, INF },
                        { INF, INF, 0, 1 },
                        { INF, INF, INF, 0 } };
 
    // Print the solution
    floydWarshall(graph);
    return 0;
}

Java

import java.util.*;
 
public class GFG {
    // Number of vertices in the graph
    static final int V = 4;
    static final int INF = 99999;
 
    // A utility function to find the vertex with minimum
    // distance value, from the set of vertices not yet
    // included in shortest path tree
    static int minDistance(int[] dist, boolean[] sptSet)
    {
        // Initialize min value
        int min = INF, min_index = -1;
 
        for (int v = 0; v < V; v++)
            if (!sptSet[v] && dist[v] <= min) {
                min = dist[v];
                min_index = v;
            }
        return min_index;
    }
 
    // A utility function to print the constructed distance
    // array
    static void printSolution(int[][] dist)
    {
        System.out.println(
            "Following matrix shows the shortest distances "
            + "between every pair of vertices:");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][j] == INF)
                    System.out.printf("%7s", "INF");
                else
                    System.out.printf("%7d", dist[i][j]);
            }
            System.out.println();
        }
    }
 
    // Solves the all-pairs shortest path problem using
    // Floyd Warshall algorithm
    static void floydWarshall(int[][] graph)
    {
        int[][] dist = new int[V][V];
        int i, j, k;
 
        /* Initialize the solution matrix same as input
           graph matrix. Or we can say the initial values of
           shortest distances are based on shortest paths
           considering no intermediate vertex. */
        for (i = 0; i < V; i++)
            for (j = 0; j < V; j++)
                dist[i][j] = graph[i][j];
 
        /* Add all vertices one by one to the set of
          intermediate vertices.
          ---> Before start of a iteration, we have shortest
          distances between all pairs of vertices such that
          the shortest distances consider only the vertices
          in set {0, 1, 2, .. k-1} as intermediate vertices.
          ----> After the end of a iteration, vertex no. k
          is added to the set of intermediate vertices and
          the set becomes {0, 1, 2, .. k} */
        for (k = 0; k < V; k++) {
            // Pick all vertices as source one by one
            for (i = 0; i < V; i++) {
                // Pick all vertices as destination for the
                // above picked source
                for (j = 0; j < V; j++) {
                    // If vertex k is on the shortest path
                    // from i to j, then update the value of
                    // dist[i][j]
                    if (dist[i][k] + dist[k][j]
                        < dist[i][j])
                        dist[i][j]
                            = dist[i][k] + dist[k][j];
                }
            }
        }
 
        // Print the shortest distance matrix
        printSolution(dist);
    }
 
    // driver program to test above function
    public static void main(String[] args)
    {
        /* Let us create the following weighted graph
                10
           (0)------->(3)
            |         /|\
          5 |          |
            |          | 1
           \|/         |
           (1)------->(2)
                3           */
        int[][] graph = { { 0, 5, INF, 10 },
                          { INF, 0, 3, INF },
                          { INF, INF, 0, 1 },
                          { INF, INF, INF, 0 } };
        // Print the solution
        floydWarshall(graph);
    }
}

Python3

import sys
 
# Number of vertices in the graph
V = 4
 
# A utility function to find the vertex with minimum distance value, from
# the set of vertices not yet included in shortest path tree
 
 
def minDistance(dist, sptSet):
    # Initialize min value
    min_val = sys.maxsize
    min_index = 0
 
    for v in range(V):
        if sptSet[v] == False and dist[v] <= min_val:
            min_val = dist[v]
            min_index = v
 
    return min_index
 
# A utility function to print the constructed distance array
 
 
def printSolution(dist):
    print("Following matrix shows the shortest distances between every pair of vertices")
    for i in range(V):
        for j in range(V):
            if dist[i][j] == sys.maxsize:
                print("{:>7s}".format("INF"), end="")
            else:
                print("{:>7d}".format(dist[i][j]), end="")
        print()
 
# Solves the all-pairs shortest path problem using Johnson's algorithm
 
 
def floydWarshall(graph):
    dist = [[0 for x in range(V)] for y in range(V)]
 
    # Initialize the solution matrix same as input graph matrix. Or
    # we can say the initial values of shortest distances are based
    # on shortest paths considering no intermediate vertex.
    for i in range(V):
        for j in range(V):
            dist[i][j] = graph[i][j]
 
    # Add all vertices one by one to the set of intermediate vertices.
    # Before start of a iteration, we have shortest distances between all
    # pairs of vertices such that the shortest distances consider only the
    # vertices in set {0, 1, 2, .. k-1} as intermediate vertices.
    # After the end of a iteration, vertex no. k is added to the set of
    # intermediate vertices and the set becomes {0, 1, 2, .. k}
    for k in range(V):
        # Pick all vertices as source one by one
        for i in range(V):
            # Pick all vertices as destination for the
            # above picked source
            for j in range(V):
                # If vertex k is on the shortest path from
                # i to j, then update the value of dist[i][j]
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
 
    # Print the shortest distance matrix
    printSolution(dist)
 
 
# driver program to test above function
if __name__ == "__main__":
 
    ''' Let us create the following weighted graph
            10
       (0)------->(3)
        |         /|\
      5 |          |
        |          | 1
       \|/         |
       (1)------->(2)
            3           '''
 
    graph = [[0,   5,  sys.maxsize, 10],
             [sys.maxsize, 0,   3, sys.maxsize],
             [sys.maxsize, sys.maxsize, 0,   1],
             [sys.maxsize, sys.maxsize, sys.maxsize, 0]
             ]
 
    # Print the solution
    floydWarshall(graph)

C#

using System;
 
class Program {
    const int INF = 99999;
    // Number of vertices in the graph
    const int V = 4;
    // A utility function to find the vertex with minimum
    // distance value, from the set of vertices not yet
    // included in shortest path tree
    static int MinDistance(int[] dist, bool[] sptSet)
    {
        // Initialize min value
        int min = int.MaxValue, min_index = 0;
 
        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && dist[v] <= min) {
                min = dist[v];
                min_index = v;
            }
        }
 
        return min_index;
    }
    // A utility function to print the constructed distance
    // array
    static void PrintSolution(int[, ] dist)
    {
        Console.WriteLine(
            "Following matrix shows the shortest distances"
            + " between every pair of vertices");
 
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i, j] == INF) {
                    Console.Write("{0,7}", "INF");
                }
                else {
                    Console.Write("{0,7}", dist[i, j]);
                }
            }
 
            Console.WriteLine();
        }
    }
    // Solves the all-pairs shortest path problem using
    // Johnson's algorithm
    static void FloydWarshall(int[, ] graph)
    {
        int[, ] dist = new int[V, V];
        /* Initialize the solution matrix same as input
           graph matrix. Or we can say the initial values of
           shortest distances are based on shortest paths
           considering no intermediate vertex. */
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i, j] = graph[i, j];
            }
        }
        /* Add all vertices one by one to the set of
           intermediate vertices.
              ---> Before start of a iteration, we have
           shortest distances between all pairs of vertices
           such that the shortest distances consider only
           the vertices in set {0, 1, 2, .. k-1} as
           intermediate vertices.
              ----> After the end of a iteration, vertex no.
           k is added to the set of intermediate vertices
           and the set becomes {0, 1, 2, .. k} */
        for (int k = 0; k < V; k++) {
            // Pick all vertices as source one by one
            for (int i = 0; i < V; i++) {
                // Pick all vertices as destination for the
                // above picked source
                for (int j = 0; j < V; j++) {
                    // If vertex k is on the shortest path
                    // from
                    // i to j, then update the value of
                    // dist[i][j]
                    if (dist[i, k] + dist[k, j]
                        < dist[i, j]) {
                        dist[i, j]
                            = dist[i, k] + dist[k, j];
                    }
                }
            }
        }
        // Print the shortest distance matrix
        PrintSolution(dist);
    }
    // driver program to test above function
    static void Main(string[] args)
    {
        /* Let us create the following weighted graph
           10
      (0)------->(3)
       |         /|\
     5 |          |
       |          | 1
      \|/         |
      (1)------->(2)
           3           */
        int[, ] graph
            = new int[, ] { { 0, 5, INF, 10 },
                            { INF, 0, 3, INF },
                            { INF, INF, 0, 1 },
                            { INF, INF, INF, 0 } };
        // Print the solution
        FloydWarshall(graph);
    }
}
 
// This code is contributed by NarasingaNikhil

Javascript

const V = 4;
 
// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
function minDistance(dist, sptSet) {
    // Initialize min value
    let min_val = Number.MAX_SAFE_INTEGER;
    let min_index = 0;
 
    for (let v = 0; v < V; v++) {
        if (sptSet[v] == false && dist[v] <= min_val) {
            min_val = dist[v];
            min_index = v;
        }
    }
 
    return min_index;
}
 
// A utility function to print the constructed distance array
function printSolution(dist) {
    console.log("Following matrix shows the shortest distances between every pair of vertices");
    for (let i = 0; i < V; i++) {
        for (let j = 0; j < V; j++) {
            if (dist[i][j] == Number.MAX_SAFE_INTEGER) {
                process.stdout.write("INF".padStart(7));
            } else {
                process.stdout.write(dist[i][j].toString().padStart(7));
            }
        }
        console.log();
    }
}
 
// Solves the all-pairs shortest path problem using Johnson's algorithm
function floydWarshall(graph) {
    let dist = new Array(V).fill().map(() => new Array(V).fill(0));
 
    // Initialize the solution matrix same as input graph matrix. Or
    // we can say the initial values of shortest distances are based
    // on shortest paths considering no intermediate vertex.
    for (let i = 0; i < V; i++) {
        for (let j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }
 
    // Add all vertices one by one to the set of intermediate vertices.
    // Before start of a iteration, we have shortest distances between all
    // pairs of vertices such that the shortest distances consider only the
    // vertices in set {0, 1, 2, .. k-1} as intermediate vertices.
    // After the end of a iteration, vertex no. k is added to the set of
    // intermediate vertices and the set becomes {0, 1, 2, .. k}
    for (let k = 0; k < V; k++) {
 
        // Pick all vertices as source one by one
        for (let i = 0; i < V; i++) {
 
            // Pick all vertices as destination for the
            // above picked source
            for (let j = 0; j < V; j++) {
 
                // If vertex k is on the shortest path from
                // i to j, then update the value of dist[i][j]
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
 
    printSolution(dist);
}
 
if (require.main === module) {
    /** Let us create the following weighted graph 
     *      10 
     *   (0)------->(3) 
     *     |         /|\ 
     *   5 |          | 
     *     |          | 1 
     *   \|/         | 
     *   (1)------->(2) 
     *        3           */
     
    const graph = [
        [0, 5, Number.MAX_SAFE_INTEGER, 10],
        [Number.MAX_SAFE_INTEGER, 0, 3, Number.MAX_SAFE_INTEGER],
        [Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, 0, 1],
        [Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, 0]
    ];
 
    floydWarshall(graph);
}

Output

Following matrix shows the shortest distances between every pair of vertices 
      0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0

Time Complexity: The main steps in the algorithm are Bellman-Ford Algorithm called once and Dijkstra called V times. Time complexity of Bellman Ford is O(VE) and time complexity of Dijkstra is O(VLogV). So overall time complexity is O(V²log V + VE).

The time complexity of Johnson’s algorithm becomes the same as Floyd Warshall’s Algorithm (https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/?ref=lbp)

when the graph is complete (For a complete graph E = O(V²). But for sparse graphs, the algorithm performs much better than Floyd Warshall’s Algorithm( https://www.geeksforgeeks.org/floyd-warshall-algorithm-dp-16/?ref=lbp ).

Auxiliary Space: O(V²)

GeeksforGeeks

Improve

Floyd Warshall Algorithm

Shortest Path in Directed Acyclic Graph

BFS and DFS on Graph

Cycle in a Graph

Shortest Paths in Graph

Minimum Spanning Tree in Graph

Topological Sorting in Graph

Connectivity of Graph

Maximum flow in a Graph

Some must do problems on Graph

Johnson’s algorithm for All-pairs shortest paths

C++

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?