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:
Java Program to Implement Pairing Heap
Java Program to Find the Longest Subsequence Common to All Sequences in a Set of Sequences
A Guide to HashSet in Java
Java Program to Find the Peak Element of an Array O(n) time (Naive Method)
Giới thiệu Google Guice – Dependency injection (DI) framework
Guide to java.util.concurrent.Locks
Disable DNS caching
Prevent Brute Force Authentication Attempts with Spring Security
Jackson vs Gson
Java Program to find the maximum subarray sum using Binary Search approach
Spring Data MongoDB Transactions
Guide to System.gc()
Java Program to Implement Quick sort
Kiểu dữ liệu Ngày Giờ (Date Time) trong java
Java Program to implement Sparse Vector
Java Program to Implement ArrayDeque API
Receive email using IMAP
Java Program to Check if a Directed Graph is a Tree or Not Using DFS
Java Program to Implement HashSet API
Java Program to Find Maximum Element in an Array using Binary Search
Introduction to Using Thymeleaf in Spring
Java Program to Implement the MD5 Algorithm
Java Program to implement Dynamic Array
Shuffling Collections In Java
Java Program to Generate N Number of Passwords of Length M Each
Comparing Dates in Java
Spring Web Annotations
Java Program to Implement the Hungarian Algorithm for Bipartite Matching
Hashing a Password in Java
Java Program to Implement Sorted List
Java Program to Implement Double Ended Queue
Guide to java.util.concurrent.BlockingQueue