Implement Johnson’s algorithm for All-pairs in C++

In this tutorial, we will learn to Implement Johnson’s algorithm for All-pairs the shortest paths in C++. At final, we will implement code.

Johnson’s algorithm for All-pairs the shortest paths.

Algorithm for the Johnson:

Let the given graph be G. A new vertex v should be added to the graph, Later add edges from a new vertex to all vertices of graph G. The modified graph be G.

Use the bellman-ford algorithm on G with v as a source point. The distances calculated by Bellman-Ford be h[0], h[1],..h[V-1]. Return it if you found a negative weighted cycle. Make a note that the negative weight cycle cannot be created by new vertex v as there is no edge to v. All edges are from v.

Reweights the edges of the original graph. For each edge (x, y), assign the new weight as “original weight + h[x] – h[y].”

Run the Dijkstra algorithm for every vertex after removing the added vertex s.

IMPLEMENTING CODE.

#include<iostream>
#define INF 9999
using namespace std;
int min(int a, int b);
int cost[10][10], adj[10][10];
inline int min(int a, int b){
   return(a<b)?a:b;
}
 
main() {
   int vert,edge,i,j,k,c;
   cout<< "Enter no of vertices: ";
   cin>> vert;
   cout<< "Enter no of edges: ";
   cin>> edge;
   cout<< "Enter the EDGE Costs:\n";
   for(k = 1; k <= edge; k++){
      cin>>i>>j>>c;
      adj[i][j]=cost[i][j]=c;
   }
   for(i = 1; i <= vert; i++)
      for(j = 1; j <= vert; j++) {
         if(adj[i][j] == 0 && i != j)
            adj[i][j] = INF;
      }
   for (k = 1; k <= vert; k++)
      for (i = 1; i <= vert; i++)
         for (j = 1; j <= vert; j++)
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
   cout << "Resultant adj matrix\n";
   for (i = 1; i <= vert; i++) {
      for (j = 1; j <= vert; j++) {
            if (adj[i][j]!=INF)
               cout<<adj[i][j]<< " ";
      }
      cout << "\n";
   }
}

OUTPUT:

Enter no of vertices: 3
Enter no of edges: 5
Enter the EDGE Costs:
1 2 8
2 1 12
1 3 22
3 1 6
2 3 4
Resultant adj matrix
0 8 12
10 0 4
6 14 0

Also read: partial_sort() function in C++ Algorithm