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:
Java Program to Implement Find all Forward Edges in a Graph
The Order of Tests in JUnit
Spring Security with Maven
Guide to Guava Table
Java Byte Array to InputStream
Hashtable trong java
Java Program to Check if a Given Graph Contain Hamiltonian Cycle or Not
Java Program to Implement LinkedList API
HttpClient Timeout
Java Program to Implement Graph Coloring Algorithm
Java Program to Implement Hopcroft Algorithm
Spring Boot Annotations
Life Cycle of a Thread in Java
Spring Data MongoDB Transactions
Introduction to Using FreeMarker in Spring MVC
Spring Boot Change Context Path
Giới thiệu Google Guice – Injection, Scope
Lập trình đa luồng trong Java (Java Multi-threading)
Serialize Only Fields that meet a Custom Criteria with Jackson
Receive email using IMAP
Java String to InputStream
Java Program to Implement Threaded Binary Tree
Spring Boot - Exception Handling
Java Program to Find Maximum Element in an Array using Binary Search
Spring MVC Setup with Kotlin
An Introduction to ThreadLocal in Java
Spring Cloud AWS – RDS
Spring REST API + OAuth2 + Angular
Java 8 Stream findFirst() vs. findAny()
Java Switch Statement
Java Program to Implement Splay Tree
Java Program to Describe the Representation of Graph using Incidence Matrix