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
The described algorithm is called Floyd-Warshall Algorithm.