Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem Statement
2.
Approach
3.
Algorithm
4.
Code
5.
Time Complexity
6.
Space complexity
7.
FAQs
8.
Key Takeaways
Last Updated: Mar 27, 2024

Johnson’s Algorithm for All-Pairs Shortest Paths

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Problem Statement

 

You are given a weighted directed graph having N vertices and M edges.  You have to find the shortest distance between every pair of vertices. The weight of the edges in the graph can be negative.

Approach

 

For a vertex, we can find the shortest distance to all the other vertices in the given graph using the Dijkstra algorithm with minimum priority queue in O(V + E log V) time complexity. Applying the algorithm for every vertex in the graph, we can find the shortest distance between all the pairs in O(V^2 + VE log V) time complexity. 

The problem with the Dijkstra algorithm is that we can't apply it to the graphs having a negative weight edge. 

The idea of Johnson's algorithm is that if we can transform the given graph to a graph so that all the edge weights are positive, we can apply the Dijkstra Algorithm.

 

Can we add the minimum weight edge to all the edges??

The most straightforward approach to make all the edge weights positive is to add the minimum weight edge to all the edges. But the problem with this approach is that the shortest path may not remain the shortest after adding the minimum weight edge to all the vertices. See the example below for a better understanding -
 

In the example p1 and p2 are two distinct paths between node 1 and 2 and initially p1 < p2. But after adding (absolute value of minimum weight) to all the edges p2 < p1

So we have to increment each edge weight in such a way that all the edge weights become positive, and all the paths between every pair of vertices increased by the same amount so that the shortest path doesn't change.

Johnson's algorithm achieves that by assigning each vertex an integer. Let there be two vertices, u and v,  such that there is an edge (u -> v) between them. If C[u] and C[v] are the integers assigned to and v, respectively, then the algorithm increases the edge weight by (C[u] - C[v]).


Why does this works??

As shown in the example above, for two vertices and v, all the path lengths will increase by C[u] -C[v], and all the other values of C[] get canceled out.


How to calculate the values of C[]?? 

To calculate the value C[] for each vertex, add a new vertex in the graph and connect it to all the other vertices by the edges of weight zero directed from the new vertex to the existing vertex. This does not change the shortest path between any pair.

Now, use the Bellman-Ford algorithm to find the shortest distance to every vertex from the new vertex. The shortest distance values are values of c[].

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm

 

Let us consider the following graph - 
 

Step 1 - Add a new vertex 0 to the given graph, add edges of weight 0 from the new vertex to all the existing vertices.

Step 2 - Find the shortest path from the new vertex to all the other existing vertices using the Bellman-Ford algorithm.

The shortest distance values are values of c[].

Step 3 - For every pair of vertices u and v, having an edge (u -> v), add C[u] - C[v] to the edge weight.

Step 4 - Remove the added vertex (vertex 0) and apply Dijkstra's algorithm for every vertex.  

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M = 500;
/*
   Adjacency List
   edge = {u, v, w}
   g[u].push_back({v, w})
*/
vector <pair<int, int>> G[M];

vector <int> bellmanFord(int &N, vector <vector<int>> edges){
   /*
       Step 1 - Add a new vertex 0 to the given graph, add edges of  
       weight 0 from the new vertex to all the existing vertices.
       edge = {0, u, 0} (1 <= u <= N)
   */
   for(int i = 1; i <= N; i++){
       edges.push_back({0, i, 0});
   }
   /*
       Step 2 - Find the shortest path from the new vertex to all the other 
       existing vertices using the Bellman-Ford algorithm.
   */
   vector <int> d(N + 1, INT_MAX);
   d[0] = 0;
   while(true){
       bool check = false;
       for(auto e : edges){
           int u = e[0];
           int v = e[1];
           int w = e[2];
           if(d[v] > d[u] + w){
               d[v] = d[u] + w;
               check = true;
           }
       }
       if(!check)
           break;
   }
   //The shortest distance values are values of c[].
   return d;
}

//Dijkstra Algorithm
void Dijkstra(int src, vector <vector<int>> &path, int &N){
   
   priority_queue<pair<int, int>> pq;
   vector <int> vis(N + 1);
   path[src][src] = 0;
   pq.push({0, src});
   while(!pq.empty()){
       int f = pq.top().second;
       pq.pop();
       if(!vis[f]){
           vis[f] = true;
           for(auto u : G[f]){
               int s = u.first;
               int w = u.second;
               if(path[src][f] + w < path[src][s]){
                   path[src][s] = path[src][f] + w;
                   pq.push({-path[src][s], s});
               }
           }
       }
   }
}

signed main(){
   //vertices, edges
   int N, M;
   cin >> N >> M;
   /*
       vector to store edges
       edge - (u->v)
       weight - w
       edges.push_back({u, v, w})
   */
   vector <vector<int>> edges;
   for(int i = 1; i <= M; i++){
       int u, v, w;
       cin >> u >> v >> w;
       edges.push_back({u, v, w});
   }
   //The shortest distance values are values of c[].
   vector <int> C = bellmanFord(N, edges);
   for(int i = 0; i < M; i++){
       int u = edges[i][0];
       int v = edges[i][1];
       //For every pair of vertices u and v, having an edge (u -> v), add C[u] - C[v] to the edge weight.
       edges[i][2] += (C[u] - C[v]);
   }
   /*
       2D matrix to store all-pairs shortest path
       path[u][v] = shortest path from u to v
   */
   vector <vector<int>> path(N + 1, vector <int> (N + 1, INT_MAX));
   
   for(auto e : edges){
       G[e[0]].push_back({e[1], e[2]});
   }
   /*
   Step 4 - Remove the added vertex (vertex 0) and apply Dijkstra's algorithm for every vertex.
   */
   for(int i = 1; i <= N; i++){
       Dijkstra(i, path, N);
   }
   for(int i = 1; i <= N; i++){
       for(int j = 1; j <= N; j++){
           //If there is no path between i and j output -1
           if(path[i][j] == INT_MAX)
               cout << -1 << " ";
           //shortest path from vertex i to j
           else
               cout << path[i][j] - (C[i] - C[j]) << " ";
       }
       cout << "\n";
   }
   return 0;
}   

 

Time Complexity

We used the Bellman-Ford algorithm to calculate C[] values which runs in O(VE) time complexity, and we are running the Dijkstra algorithm for every vertex which runs in O(V + ElogV) time complexity. So the overall time complexity is O(VE + V^2 + VElogV).

 

Space complexity

As we are using the adjacency list, the space complexity depends on the number of edges. For the complete graph, it is O(V^2) which is the worst-case complexity.
 

FAQs

  1. What is the Dijkstra Algorithm?
    Dijkstra algorithm is a graph algorithm used to efficiently find the shortest path between two vertices in a graph. If implemented using the min-priority queue, its time complexity is O(V + ElogV), where E is the number of edges and V is the number of vertices in the graph.
     
  2. Why Dijkstra Algorithm doesn’t work for negative weights?
    Dijkstra's algorithm works on the fact that if all the edge weights are non-negative, then adding an edge can't make the path shorter. That's why we can't use it for graphs having negative weight edges.
     
  3. What is the Bellman-Ford Algorithm?
    Bellman-Ford algorithm finds the shortest distance to all the vertices from the given vertex in a graph data structure. Unlike the Dijkstra algorithm, it can also handle negative edges. It's worst-case time complexity is O(VE).

 

Key Takeaways

This blog covers the famous graph algorithm, the Johnson's algorithm, along with the implementation in C++.

Also, check out the other algorithms based on graphs like Floyd Warshall AlgorithmPrim's AlgorithmKruskal's Algorithm, etc.

Check out this problem - Root To Leaf Path

Don't stop here. Check out our Data Structures and Algorithm - guided path to learning Data Structures and Algorithms from scratch. We hope you found this blog useful. Feel free to let us know your thoughts in the comments section. 

 

 

Previous article
Why does Dijkstra’s algorithm fail on negative weights?
Next article
Difference between the shortest and second shortest path in an Unweighted Bidirectional Graph
Live masterclass