Johnson Algorithm in C++

Last Updated : 23 Jul, 2025

Johnson’s Algorithm is an algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. It is especially useful for sparse graphs and can handle negative weights, provided there are no negative weight cycles. This algorithm uses both Bellman-Ford and Dijkstra's algorithms to achieve efficient results.

In this article, we will learn Johnson’s Algorithm and demonstrate how to implement it in C++.

Johnson’s Algorithm for All-Pairs Shortest Paths in C++

Johnson’s Algorithm transforms the original graph to ensure all edge weights are non-negative, making it possible to use Dijkstra’s algorithm. The transformation involves adding a new vertex, computing a potential function using Bellman-Ford, re-weighting the edges, and then running Dijkstra’s algorithm from each vertex.

Steps to Implement Johnson’s Algorithm in C++

Let the given graph be G. Add a new vertex s to the graph, add edges from the new vertex to all vertices of G. Let the modified graph be G’.
Run the Bellman-Ford algorithm on G’ with s as the source. Let the distances calculated by Bellman-Ford be h[0], h[1], .. h[V-1]. If we find a negative weight cycle, then return. Note that the negative weight cycle cannot be created by new vertex s as there is no edge to s. All edges are from s.
Reweight the edges of the original graph. For each edge (u, v), assign the new weight as “original weight + h[u] – h[v]”.
Remove the added vertex s and run Dijkstra’s algorithm for every vertex.

Working of Johnson Algorithm in C++

Consider the below example to understand step-by-step implementation of Johnson’s Algorithm.

Step 1: Add a New Vertex
We add a new vertex 4 and connect it to all other vertices with edges of weight 0.

Step 2: Compute Potential Function using Bellman-Ford
Using the Bellman-Ford algorithm from vertex 4, we compute the shortest path estimates (potential function):
Distances from vertex 4 to vertices 0, 1, 2, and 3 are 0, −5, −1, and 0, respectively.
Therefore, h[]={0,−5,−1,0}

Step 3: Re-weight the Edges
Re-weight the edges using the formula 
w′(u,v) = w(u,v) + h[u] − h[v]
After re-weighting, the edges are as follows:
Edge (0,1): Original weight = −5, New weight = −5+0−(−5) = 0
Edge (1,2): Original weight = 4, New weight = 4+(−5)−(−1) = 0
Edge (2,3): Original weight = 1, New weight = 1+(−1)−0 = 0
Edge (0,3): Original weight = 3, New weight = 3+0−0 = 3
Edge (3,2): Original weight = 2, New weight = 2+0−(−1) = 3

Step 4: Run Dijkstra's Algorithm
Run Dijkstra's algorithm from each vertex in the re-weighted graph to find the shortest paths. 
Since all re-weighted edge weights are non-negative, Dijkstra's algorithm can be used efficiently.

C++ Program to Implement Johnson’s Algorithm

The below program illustrate the implementation of Johnson’s Algorithm in C++.

C++

// C++ program to implement Johnson's Algorithm for finding the shortest paths // between all pairs of vertices in a graph that may contain negative weights. #include <algorithm> #include <iostream> #include <limits> #include <vector> #define INF numeric_limits<int>::max() using namespace std; // Function to find the vertex with the minimum distance that has not yet been included in the shortest path // tree int Min_Distance(const vector<int> &dist, const vector<bool> &visited) {  int min = INF, min_index;  for (int v = 0; v < dist.size(); ++v)  {  if (!visited[v] && dist[v] <= min)  {  min = dist[v];  min_index = v;  }  }  return min_index; } // Function to perform Dijkstra's algorithm on the modified graph void Dijkstra_Algorithm(const vector<vector<int>> &graph, const vector<vector<int>> &altered_graph,  int source) {  // Number of vertices  int V = graph.size();  // Distance from source to each vertex  vector<int> dist(V, INF);  // Track visited vertices  vector<bool> visited(V, false);  // Distance to source itself is 0  dist[source] = 0;  // Compute shortest path for all vertices  for (int count = 0; count < V - 1; ++count)  {  // Select the vertex with the minimum distance that hasn't been visited  int u = Min_Distance(dist, visited);  // Mark this vertex as visited  visited[u] = true;  // Update the distance value of the adjacent vertices of the selected vertex  for (int v = 0; v < V; ++v)  {  if (!visited[v] && graph[u][v] != 0 && dist[u] != INF && dist[u] + altered_graph[u][v] < dist[v])  {  dist[v] = dist[u] + altered_graph[u][v];  }  }  }  // Print the shortest distances from the source  cout << "Shortest Distance from vertex " << source << ":\n";  for (int i = 0; i < V; ++i)  {  cout << "Vertex " << i << ": " << (dist[i] == INF ? "INF" : to_string(dist[i])) << endl;  } } // Function to perform Bellman-Ford algorithm to find shortest distances // from a source vertex to all other vertices vector<int> BellmanFord_Algorithm(const vector<vector<int>> &edges, int V) {  // Distance from source to each vertex  vector<int> dist(V + 1, INF);  // Distance to the new source vertex (added vertex) is 0  dist[V] = 0;  // Add a new source vertex to the graph and connect it to all original vertices with 0 weight edges  vector<vector<int>> edges_with_extra(edges);  for (int i = 0; i < V; ++i)  {  edges_with_extra.push_back({V, i, 0});  }  // Relax all edges |V| - 1 times  for (int i = 0; i < V; ++i)  {  for (const auto &edge : edges_with_extra)  {  if (dist[edge[0]] != INF && dist[edge[0]] + edge[2] < dist[edge[1]])  {  dist[edge[1]] = dist[edge[0]] + edge[2];  }  }  }  // Return distances excluding the new source vertex  return vector<int>(dist.begin(), dist.begin() + V); } // Function to implement Johnson's Algorithm void JohnsonAlgorithm(const vector<vector<int>> &graph) {  // Number of vertices  int V = graph.size();  vector<vector<int>> edges;  // Collect all edges from the graph  for (int i = 0; i < V; ++i)  {  for (int j = 0; j < V; ++j)  {  if (graph[i][j] != 0)  {  edges.push_back({i, j, graph[i][j]});  }  }  }  // Get the modified weights from Bellman-Ford algorithm  vector<int> altered_weights = BellmanFord_Algorithm(edges, V);  vector<vector<int>> altered_graph(V, vector<int>(V, 0));  // Modify the weights of the edges to remove negative weights  for (int i = 0; i < V; ++i)  {  for (int j = 0; j < V; ++j)  {  if (graph[i][j] != 0)  {  altered_graph[i][j] = graph[i][j] + altered_weights[i] - altered_weights[j];  }  }  }  // Print the modified graph with re-weighted edges  cout << "Modified Graph:\n";  for (const auto &row : altered_graph)  {  for (int weight : row)  {  cout << weight << ' ';  }  cout << endl;  }  // Run Dijkstra's algorithm for every vertex as the source  for (int source = 0; source < V; ++source)  {  cout << "\nShortest Distance with vertex " << source << " as the source:\n";  Dijkstra_Algorithm(graph, altered_graph, source);  } } // Main function to test the Johnson's Algorithm implementation int main() {  // Define a graph with possible negative weights  vector<vector<int>> graph = {{0, -5, 2, 3}, {0, 0, 4, 0}, {0, 0, 0, 1}, {0, 0, 0, 0}};  // Execute Johnson's Algorithm  JohnsonAlgorithm(graph);  return 0; }

Output

Modified Graph: 0 0 3 3 0 0 0 0 0 0 0 0 0 0 0 0 Shortest Distance with vertex 0 as the source: Shortest Distance from vertex 0: Vertex 0: 0 Vertex 1: 0 Vertex 2: 0 Vertex 3: 0 Shortest Distance with vertex 1 as the source: Shortest Distance from vertex 1: Vertex 0: INF Vertex 1: 0 Vertex 2: 0 Vertex 3: 0 Shortest Distance with vertex 2 as the source: Shortest Distance from vertex 2: Vertex 0: INF Vertex 1: INF Vertex 2: 0 Vertex 3: 0 Shortest Distance with vertex 3 as the source: Shortest Distance from vertex 3: Vertex 0: INF Vertex 1: INF Vertex 2: INF Vertex 3: 0

Time Complexity: The main steps in the algorithm are Bellman-Ford Algorithm called once and Dijkstra called V times. Time complexity of Bellman Ford is O(VE) and time complexity of Dijkstra is O(VLogV). So overall time complexity is O(V2log V + VE).

The time complexity of Johnson’s algorithm becomes the same as Floyd Warshall’s Algorithm

when the graph is complete (For a complete graph E = O(V2). But for sparse graphs, the algorithm performs much better than Floyd Warshall’s Algorithm.

Auxiliary Space: O(V2)