Johnson’s Algorithm for All-Pairs Shortest Paths

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.
 

• Prims and Kruskal Algorithm

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 Algorithm, Prim's Algorithm, Kruskal'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.