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.
Here is the source code of the Java program to implement Johnson algorithm. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
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[destination] = result[destination] + potential[destination] - potential; } } 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[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[destination] = adjacencyMatrix[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[destination] = adjacencyMatrix[destination] + potential - 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 = 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 = true; distances = 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; } }
$javac JohnsonsAlgorithm .java $java JohnsonsAlgorithm 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
Related posts:
Adding a Newline Character to a String in Java
Login For a Spring Web App – Error Handling and Localization
Spring Boot - Service Components
OAuth2 Remember Me with Refresh Token
Java Program to Implement Red Black Tree
Converting a Stack Trace to a String in Java
Java Program to Implement Stack using Linked List
Spring Boot - Cloud Configuration Server
Java Program to Represent Graph Using Adjacency List
Spring Boot - Eureka Server
Java Program to Find Transitive Closure of a Graph
The Registration Process With Spring Security
Sắp xếp trong Java 8
Spring Boot - Apache Kafka
Java Program to find the number of occurrences of a given number using Binary Search approach
Request a Delivery / Read Receipt in Javamail
Guide to the Volatile Keyword in Java
LinkedList trong java
How to Define a Spring Boot Filter?
Java Program to Implement the Hill Cypher
Spring Cloud – Adding Angular
Assert an Exception is Thrown in JUnit 4 and 5
Read an Outlook MSG file
Java Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm
Java Program to Perform Naive String Matching
Java Program to Implement Segment Tree
Guide to java.util.concurrent.Locks
A Guide to ConcurrentMap
Java – Combine Multiple Collections
Merging Streams in Java
The Modulo Operator in Java
Java 8 Stream API Analogies in Kotlin