|
|
|
|
|
/*This Java program is to Implement Johnson’s algorithm. Johnson’s algorithm is a way to find the shortest paths between all pairs of vertices in a sparse, edge weighted, directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist. 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.*/
|
|
|
|
|
|
|
|
|
|
|
|
import java.util.InputMismatchException;
|
|
|
|
|
|
import java.util.Scanner;
|
|
|
|
|
|
public class JohnsonsAlgorithm
|
|
|
|
|
|
{
|
|
|
|
|
|
private int SOURCE_NODE;
|
|
|
|
|
|
private int numberOfNodes;
|
|
|
|
|
|
private int augmentedMatrix[][];
|
|
|
|
|
|
private int potential[];
|
|
|
|
|
|
private BellmanFord bellmanFord;
|
|
|
|
|
|
private DijkstraShortesPath dijsktraShortesPath;
|
|
|
|
|
|
private int[][] allPairShortestPath;
|
|
|
|
|
|
|
|
|
|
|
|
public static final int MAX_VALUE = 999;
|
|
|
|
|
|
|
|
|
|
|
|
public JohnsonsAlgorithm(int numberOfNodes)
|
|
|
|
|
|
{
|
|
|
|
|
|
this.numberOfNodes = numberOfNodes;
|
|
|
|
|
|
augmentedMatrix = new int[numberOfNodes + 2][numberOfNodes + 2];
|
|
|
|
|
|
SOURCE_NODE = numberOfNodes + 1;
|
|
|
|
|
|
potential = new int[numberOfNodes + 2];
|
|
|
|
|
|
bellmanFord = new BellmanFord(numberOfNodes + 1);
|
|
|
|
|
|
dijsktraShortesPath = new DijkstraShortesPath(numberOfNodes);
|
|
|
|
|
|
allPairShortestPath = new int[numberOfNodes + 1][numberOfNodes + 1];
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
public void johnsonsAlgorithms(int adjacencyMatrix[][])
|
|
|
|
|
|
{
|
|
|
|
|
|
computeAugmentedGraph(adjacencyMatrix);
|
|
|
|
|
|
bellmanFord.BellmanFordEvaluation(SOURCE_NODE, augmentedMatrix);
|
|
|
|
|
|
potential = bellmanFord.getDistances();
|
|
|
|
|
|
int reweightedGraph[][] = reweightGraph(adjacencyMatrix);
|
|
|
|
|
|
for (int i = 1; i <= numberOfNodes; i++)
|
|
|
|
|
|
{
|
|
|
|
|
|
for (int j = 1; j <= numberOfNodes; j++)
|
|
|
|
|
|
{
|
|
|
|
|
|
System.out.print(reweightedGraph[i][j] + "\t");
|
|
|
|
|
|
}
|
|
|
|
|
|
System.out.println();
|
|
|
|
|
|
}
|
|
|
|
|
|
for (int source = 1; source <= numberOfNodes; source++)
|
|
|
|
|
|
{
|
|
|
|
|
|
dijsktraShortesPath.dijkstraShortestPath(source, reweightedGraph);
|
|
|
|
|
|
int[] result = dijsktraShortesPath.getDistances();
|
|
|
|
|
|
for (int destination = 1; destination <= numberOfNodes; destination++)
|
|
|
|
|
|
{
|
|
|
|
|
|
allPairShortestPath[source][destination] = result[destination]
|
|
|
|
|
|
+ potential[destination] - potential[source];
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
System.out.println();
|
|
|
|
|
|
for (int i = 1; i<= numberOfNodes; i++)
|
|
|
|
|
|
{
|
|
|
|
|
|
System.out.print("\t"+i);
|
|
|
|
|
|
}
|
|
|
|
|
|
System.out.println();
|
|
|
|
|
|
for (int source = 1; source <= numberOfNodes; source++)
|
|
|
|
|
|
{
|
|
|
|
|
|
System.out.print( source +"\t" );
|
|
|
|
|
|
for (int destination = 1; destination <= numberOfNodes; destination++)
|
|
|
|
|
|
{
|
|
|
|
|
|
System.out.print(allPairShortestPath[source][destination]+ "\t");
|
|
|
|
|
|
}
|
|
|
|
|
|
System.out.println();
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
private void computeAugmentedGraph(int adjacencyMatrix[][])
|
|
|
|
|
|
{
|
|
|
|
|
|
for (int source = 1; source <= numberOfNodes; source++)
|
|
|
|
|
|
{
|
|
|
|
|
|
for (int destination = 1; destination <= numberOfNodes; destination++)
|
|
|
|
|
|
{
|
|
|
|
|
|
augmentedMatrix[source][destination] = adjacencyMatrix[source][destination];
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
for (int destination = 1; destination <= numberOfNodes; destination++)
|
|
|
|
|
|
{
|
|
|
|
|
|
augmentedMatrix[SOURCE_NODE][destination] = 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
private int[][] reweightGraph(int adjacencyMatrix[][])
|
|
|
|
|
|
{
|
|
|
|
|
|
int[][] result = new int[numberOfNodes + 1][numberOfNodes + 1];
|
|
|
|
|
|
for (int source = 1; source <= numberOfNodes; source++)
|
|
|
|
|
|
{
|
|
|
|
|
|
for (int destination = 1; destination <= numberOfNodes; destination++)
|
|
|
|
|
|
{
|
|
|
|
|
|
result[source][destination] = adjacencyMatrix[source][destination]
|
|
|
|
|
|
+ potential[source] - potential[destination];
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
return result;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
public static void main(String... arg)
|
|
|
|
|
|
{
|
|
|
|
|
|
int adjacency_matrix[][];
|
|
|
|
|
|
int number_of_vertices;
|
|
|
|
|
|
Scanner scan = new Scanner(System.in);
|
|
|
|
|
|
try
|
|
|
|
|
|
{
|
|
|
|
|
|
System.out.println("Enter the number of vertices");
|
|
|
|
|
|
number_of_vertices = scan.nextInt();
|
|
|
|
|
|
adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
|
|
|
|
|
|
System.out.println("Enter the Weighted Matrix for the graph");
|
|
|
|
|
|
for (int i = 1; i <= number_of_vertices; i++)
|
|
|
|
|
|
{
|
|
|
|
|
|
for (int j = 1; j <= number_of_vertices; j++)
|
|
|
|
|
|
{
|
|
|
|
|
|
adjacency_matrix[i][j] = scan.nextInt();
|
|
|
|
|
|
if (i == j)
|
|
|
|
|
|
{
|
|
|
|
|
|
adjacency_matrix[i][j] = 0;
|
|
|
|
|
|
continue;
|
|
|
|
|
|
}
|
|
|
|
|
|
if (adjacency_matrix[i][j] == 0)
|
|
|
|
|
|
{
|
|
|
|
|
|
adjacency_matrix[i][j] = MAX_VALUE;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
JohnsonsAlgorithm johnsonsAlgorithm = new JohnsonsAlgorithm(number_of_vertices);
|
|
|
|
|
|
johnsonsAlgorithm.johnsonsAlgorithms(adjacency_matrix);
|
|
|
|
|
|
}
|
|
|
|
|
|
catch (InputMismatchException inputMismatch)
|
|
|
|
|
|
{
|
|
|
|
|
|
System.out.println("Wrong Input Format");
|
|
|
|
|
|
}
|
|
|
|
|
|
scan.close();
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
class BellmanFord
|
|
|
|
|
|
{
|
|
|
|
|
|
private int distances[];
|
|
|
|
|
|
private int numberofvertices;
|
|
|
|
|
|
|
|
|
|
|
|
public static final int MAX_VALUE = 999;
|
|
|
|
|
|
|
|
|
|
|
|
public BellmanFord(int numberofvertices)
|
|
|
|
|
|
{
|
|
|
|
|
|
this.numberofvertices = numberofvertices;
|
|
|
|
|
|
distances = new int[numberofvertices + 1];
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
public void BellmanFordEvaluation(int source, int adjacencymatrix[][])
|
|
|
|
|
|
{
|
|
|
|
|
|
for (int node = 1; node <= numberofvertices; node++)
|
|
|
|
|
|
{
|
|
|
|
|
|
distances[node] = MAX_VALUE;
|
|
|
|
|
|
}
|
|
|
|
|
|
distances[source] = 0;
|
|
|
|
|
|
for (int node = 1; node <= numberofvertices - 1; node++)
|
|
|
|
|
|
{
|
|
|
|
|
|
for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++)
|
|
|
|
|
|
{
|
|
|
|
|
|
for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++)
|
|
|
|
|
|
{
|
|
|
|
|
|
if (adjacencymatrix[sourcenode][destinationnode] != MAX_VALUE)
|
|
|
|
|
|
{
|
|
|
|
|
|
if (distances[destinationnode] > distances[sourcenode]
|
|
|
|
|
|
+ adjacencymatrix[sourcenode][destinationnode])
|
|
|
|
|
|
{
|
|
|
|
|
|
distances[destinationnode] = distances[sourcenode]
|
|
|
|
|
|
+ adjacencymatrix[sourcenode][destinationnode];
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
for (int sourcenode = 1; sourcenode <= numberofvertices; sourcenode++)
|
|
|
|
|
|
{
|
|
|
|
|
|
for (int destinationnode = 1; destinationnode <= numberofvertices; destinationnode++)
|
|
|
|
|
|
{
|
|
|
|
|
|
if (adjacencymatrix[sourcenode][destinationnode] != MAX_VALUE)
|
|
|
|
|
|
{
|
|
|
|
|
|
if (distances[destinationnode] > distances[sourcenode]
|
|
|
|
|
|
+ adjacencymatrix[sourcenode][destinationnode])
|
|
|
|
|
|
System.out.println("The Graph contains negative egde cycle");
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
public int[] getDistances()
|
|
|
|
|
|
{
|
|
|
|
|
|
return distances;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
class DijkstraShortesPath
|
|
|
|
|
|
{
|
|
|
|
|
|
private boolean settled[];
|
|
|
|
|
|
private boolean unsettled[];
|
|
|
|
|
|
private int distances[];
|
|
|
|
|
|
private int adjacencymatrix[][];
|
|
|
|
|
|
private int numberofvertices;
|
|
|
|
|
|
|
|
|
|
|
|
public static final int MAX_VALUE = 999;
|
|
|
|
|
|
|
|
|
|
|
|
public DijkstraShortesPath(int numberofvertices)
|
|
|
|
|
|
{
|
|
|
|
|
|
this.numberofvertices = numberofvertices;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
public void dijkstraShortestPath(int source, int adjacencymatrix[][])
|
|
|
|
|
|
{
|
|
|
|
|
|
this.settled = new boolean[numberofvertices + 1];
|
|
|
|
|
|
this.unsettled = new boolean[numberofvertices + 1];
|
|
|
|
|
|
this.distances = new int[numberofvertices + 1];
|
|
|
|
|
|
this.adjacencymatrix = new int[numberofvertices + 1][numberofvertices + 1];
|
|
|
|
|
|
int evaluationnode;
|
|
|
|
|
|
for (int vertex = 1; vertex <= numberofvertices; vertex++)
|
|
|
|
|
|
{
|
|
|
|
|
|
distances[vertex] = MAX_VALUE;
|
|
|
|
|
|
}
|
|
|
|
|
|
for (int sourcevertex = 1; sourcevertex <= numberofvertices; sourcevertex++)
|
|
|
|
|
|
{
|
|
|
|
|
|
for (int destinationvertex = 1; destinationvertex <= numberofvertices; destinationvertex++)
|
|
|
|
|
|
{
|
|
|
|
|
|
this.adjacencymatrix[sourcevertex][destinationvertex]
|
|
|
|
|
|
= adjacencymatrix[sourcevertex][destinationvertex];
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
unsettled[source] = true;
|
|
|
|
|
|
distances[source] = 0;
|
|
|
|
|
|
while (getUnsettledCount(unsettled) != 0)
|
|
|
|
|
|
{
|
|
|
|
|
|
evaluationnode = getNodeWithMinimumDistanceFromUnsettled(unsettled);
|
|
|
|
|
|
unsettled[evaluationnode] = false;
|
|
|
|
|
|
settled[evaluationnode] = true;
|
|
|
|
|
|
evaluateNeighbours(evaluationnode);
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
public int getUnsettledCount(boolean unsettled[])
|
|
|
|
|
|
{
|
|
|
|
|
|
int count = 0;
|
|
|
|
|
|
for (int vertex = 1; vertex <= numberofvertices; vertex++)
|
|
|
|
|
|
{
|
|
|
|
|
|
if (unsettled[vertex] == true)
|
|
|
|
|
|
{
|
|
|
|
|
|
count++;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
return count;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
public int getNodeWithMinimumDistanceFromUnsettled(boolean unsettled[])
|
|
|
|
|
|
{
|
|
|
|
|
|
int min = MAX_VALUE;
|
|
|
|
|
|
int node = 0;
|
|
|
|
|
|
for (int vertex = 1; vertex <= numberofvertices; vertex++)
|
|
|
|
|
|
{
|
|
|
|
|
|
if (unsettled[vertex] == true && distances[vertex] < min)
|
|
|
|
|
|
{
|
|
|
|
|
|
node = vertex;
|
|
|
|
|
|
min = distances[vertex];
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
return node;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
public void evaluateNeighbours(int evaluationNode)
|
|
|
|
|
|
{
|
|
|
|
|
|
int edgeDistance = -1;
|
|
|
|
|
|
int newDistance = -1;
|
|
|
|
|
|
for (int destinationNode = 1; destinationNode <= numberofvertices; destinationNode++)
|
|
|
|
|
|
{
|
|
|
|
|
|
if (settled[destinationNode] == false)
|
|
|
|
|
|
{
|
|
|
|
|
|
if (adjacencymatrix[evaluationNode][destinationNode] != MAX_VALUE)
|
|
|
|
|
|
{
|
|
|
|
|
|
edgeDistance = adjacencymatrix[evaluationNode][destinationNode];
|
|
|
|
|
|
newDistance = distances[evaluationNode] + edgeDistance;
|
|
|
|
|
|
if (newDistance < distances[destinationNode])
|
|
|
|
|
|
{
|
|
|
|
|
|
distances[destinationNode] = newDistance;
|
|
|
|
|
|
}
|
|
|
|
|
|
unsettled[destinationNode] = true;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
public int[] getDistances()
|
|
|
|
|
|
{
|
|
|
|
|
|
return distances;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
/*
|
|
|
|
|
|
Enter the number of vertices
|
|
|
|
|
|
4
|
|
|
|
|
|
Enter the Weighted Matrix for the graph
|
|
|
|
|
|
0 0 3 0
|
|
|
|
|
|
2 0 0 0
|
|
|
|
|
|
0 7 0 1
|
|
|
|
|
|
6 0 0 0
|
|
|
|
|
|
|
|
|
|
|
|
All pair shortest path is
|
|
|
|
|
|
1 2 3 4
|
|
|
|
|
|
1 0 10 3 4
|
|
|
|
|
|
2 2 0 5 6
|
|
|
|
|
|
3 7 7 0 1
|
|
|
|
|
|
4 6 16 9 0
|
