# 1. Introduction

*Johnson’s Algorithm* is a method to find the shortest paths between every pair of vertices in a sparse, edge-weighted, directed graph. It works by using the Bellman-Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra’s algorithm to be used on the transformed graph. It is named after Donald B. Johnson, who first published the technique in 1977.

# 2. Program Steps

1. Add a new vertex to the given graph and connect all vertices of the graph to the newly added vertex with zero-weight edges.

2. Use the Bellman-Ford algorithm starting from the new vertex to find the minimum distance of all vertices.

3. Re-weight the original graph: For each edge *(u, v)* with weight *w(u, v)*, the new weight becomes *w(u, v) + h(u) – h(v)* where *h(u)* is the value from the previous step.

4. Delete the added vertex and apply Dijkstra’s algorithm for every vertex to find the shortest path to all other vertices in the re-weighted graph.

5. Finally, transform the costs back to get the correct distances.

# 3. Code Program

```
import java.util.Arrays;
public class JohnsonsAlgorithm {
static final int INF = Integer.MAX_VALUE;
static final int V = 4;
void shortestpath(int graph[][]) {
int cost[][] = new int[V + 1][V + 1];
int dist[][] = new int[V][V];
int i, j, k;
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
cost[i][j] = graph[i][j];
for (i = 0; i < V; i++)
cost[i][V] = 0;
for (i = 0; i < V; i++)
cost[V][i] = INF;
cost[V][V] = 0;
for (k = 0; k <= V; k++)
for (i = 0; i <= V; i++)
for (j = 0; j <= V; j++)
if (cost[i][k] != INF && cost[k][j] != INF && cost[i][k] + cost[k][j] < cost[i][j])
cost[i][j] = cost[i][k] + cost[k][j];
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
if (cost[i][V] + cost[V][j] < cost[i][j])
cost[i][j] = cost[i][V] + cost[V][j];
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
if (graph[i][j] != INF)
dist[i][j] = graph[i][j] + cost[i][V] - cost[j][V];
else
dist[i][j] = INF;
for (i = 0; i < V; i++) {
for (j = 0; j < V; j++) {
if (dist[i][j] == INF)
System.out.print("INF ");
else
System.out.print(dist[i][j] + " ");
}
System.out.println("");
}
}
public static void main(String[] args) {
int graph[][] = {
{0, 3, INF, 7},
{8, 0, 2, INF},
{5, INF, 0, 1},
{2, INF, INF, 0}
};
JohnsonsAlgorithm a = new JohnsonsAlgorithm();
a.shortestpath(graph);
}
}
```

### Output:

0 3 5 6 5 0 2 3 3 6 0 1 2 5 7 0

# 4. Step By Step Explanation

1. *JohnsonsAlgorithm* aims to solve the all-pairs shortest path problem in a graph with possible negative weights (but no negative weight cycles).

2. We start by adding a new vertex to the graph which connects to all other vertices. This allows us to compute minimum distance values for all vertices using Bellman-Ford.

3. The computed minimum distances are then used to re-weight the edges of the original graph, effectively removing negative weights.

4. The re-weighted graph can now be processed with *Dijkstra's algorithm* for all vertices, giving the shortest paths.

5. After calculating the shortest paths, we revert the weights back to get the correct distances.

6. In the output, the matrix represents the shortest path from one vertex to another, where *INF* indicates that no path exists.

Note: The Johnson's algorithm handles graphs with negative weights well, as long as there's no negative weight cycle. If there's a negative weight cycle, the algorithm doesn't work because there is no shortest path in such cases (the path can always be made shorter by traversing the negative cycle).