# 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, h,..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);
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;
}
for(i = 1; i <= vert; i++)
for(j = 1; j <= vert; j++) {
if(adj[i][j] == 0 && i != j)
}
for (k = 1; k <= vert; k++)
for (i = 1; i <= vert; i++)
for (j = 1; j <= vert; j++)
for (i = 1; i <= vert; i++) {
for (j = 1; j <= vert; 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