This Java program is to implement the Floyd-Warshall algorithm.The algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles) and also for finding transitive closure of a relation R.
Here is the source code of the Java program to implement Floyd-Warshall algorithm. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
import java.util.Scanner; public class FloydWarshall { private int distancematrix[][]; private int numberofvertices; public static final int INFINITY = 999; public FloydWarshall(int numberofvertices) { distancematrix = new int[numberofvertices + 1][numberofvertices + 1]; this.numberofvertices = numberofvertices; } public void floydwarshall(int adjacencymatrix[][]) { for (int source = 1; source <= numberofvertices; source++) { for (int destination = 1; destination <= numberofvertices; destination++) { distancematrix[destination] = adjacencymatrix[destination]; } } for (int intermediate = 1; intermediate <= numberofvertices; intermediate++) { for (int source = 1; source <= numberofvertices; source++) { for (int destination = 1; destination <= numberofvertices; destination++) { if (distancematrix[intermediate] + distancematrix[intermediate][destination] < distancematrix[destination]) distancematrix[destination] = distancematrix[intermediate] + distancematrix[intermediate][destination]; } } } for (int source = 1; source <= numberofvertices; source++) System.out.print("\t" + source); System.out.println(); for (int source = 1; source <= numberofvertices; source++) { System.out.print(source + "\t"); for (int destination = 1; destination <= numberofvertices; destination++) { System.out.print(distancematrix[destination] + "\t"); } System.out.println(); } } public static void main(String... arg) { int adjacency_matrix[][]; int numberofvertices; Scanner scan = new Scanner(System.in); System.out.println("Enter the number of vertices"); numberofvertices = scan.nextInt(); adjacency_matrix = new int[numberofvertices + 1][numberofvertices + 1]; System.out.println("Enter the Weighted Matrix for the graph"); for (int source = 1; source <= numberofvertices; source++) { for (int destination = 1; destination <= numberofvertices; destination++) { adjacency_matrix[destination] = scan.nextInt(); if (source == destination) { adjacency_matrix[destination] = 0; continue; } if (adjacency_matrix[destination] == 0) { adjacency_matrix[destination] = INFINITY; } } } System.out.println("The Transitive Closure of the Graph"); FloydWarshall floydwarshall = new FloydWarshall(numberofvertices); floydwarshall.floydwarshall(adjacency_matrix); scan.close(); } }
$javac FloydWarshall.java $java FloydWarshall 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 The Transitive Closure of the Graph 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:
New Features in Java 9
Spring Security and OpenID Connect
Converting a Stack Trace to a String in Java
Java Program to Implement VList
Java – Byte Array to Reader
Apache Commons Collections Bag
So sánh HashSet, LinkedHashSet và TreeSet trong Java
Java Program to Solve Tower of Hanoi Problem using Stacks
Easy Ways to Write a Java InputStream to an OutputStream
Java Program to Implement Maximum Length Chain of Pairs
Java Program to Solve Set Cover Problem assuming at max 2 Elements in a Subset
Java Program to Sort an Array of 10 Elements Using Heap Sort Algorithm
Spring Boot - Application Properties
Giới thiệu HATEOAS
How to Define a Spring Boot Filter?
How to Break from Java Stream forEach
Java Program to Create a Random Graph Using Random Edge Generation
Netflix Archaius with Various Database Configurations
Spring Boot - Database Handling
Java Multi-line String
Java Program to Implement a Binary Search Algorithm for a Specific Search Sequence
Java Program to Implement Gauss Seidel Method
Java Program to implement Dynamic Array
Copy a List to Another List in Java
Tạo số và chuỗi ngẫu nhiên trong Java
Java Program to Implement AttributeList API
Hướng dẫn Java Design Pattern – Proxy
Java Program to Implement the Vigenere Cypher
A Guide to HashSet in Java
CyclicBarrier in Java
Java Program to Implement Fermat Primality Test Algorithm
Spring Security – Reset Your Password