Java Program to Implement Warshall Algorithm

This is a Java Program to Implement Warshall Transitive closure Algorithm. Warshall’s Transitive closure algorithm is used to determine if a path exists from vertex a to vertex b for all vertex pairs (a, b) in a graph.

Here is the source code of the Java Program to Implement Warshall Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/**
 **  Java Program to Implement Warshall Algorithm
 **/
 
import java.util.Scanner;
 
/** Class Warshall **/
public class Warshall
{
    private int V;    
    private boolean[][] tc;
    /** Function to make the transitive closure **/
    public void getTC(int[][] graph)
    {
        this.V = graph.length;
        tc = new boolean[V][V];
        for (int i = 0; i < V; i++) 
        {    
            for (int j = 0; j < V; j++) 
                if (graph[i][j] != 0)
                    tc[i][j] = true;
            tc[i][i] = true;
        }
        for (int i = 0; i < V; i++) 
        {
            for (int j = 0; j < V; j++) 
            {
                if (tc[j][i]) 
                    for (int k = 0; k < V; k++) 
                        if (tc[j][i] && tc[i][k]) 
                            tc[j][k] = true;             
            }
        }
    }
    /** Funtion to display the trasitive closure **/
    public void displayTC()
    {
        System.out.println("\nTransitive closure :\n");
        System.out.print(" ");
        for (int v = 0; v < V; v++)
           System.out.print("   " + v );
        System.out.println();
        for (int v = 0; v < V; v++) 
        {
            System.out.print(v +" ");
            for (int w = 0; w < V; w++) 
            {
                if (tc[v][w]) 
                    System.out.print("  * ");
                else                  
                    System.out.print("    ");
            }
            System.out.println();
        }
    }    
 
    /** Main function **/
    public static void main (String[] args) 
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Warshall Algorithm Test\n");
        /** Make an object of Warshall class **/
        Warshall w = new Warshall();
 
        /** Accept number of vertices **/
        System.out.println("Enter number of vertices\n");
        int V = scan.nextInt();
 
        /** get graph **/
        System.out.println("\nEnter matrix\n");
        int[][] graph = new int[V][V];
        for (int i = 0; i < V; i++)
            for (int j = 0; j < V; j++)
                graph[i][j] = scan.nextInt();
 
        w.getTC(graph);
        w.displayTC();
    }
}
Warshall Algorithm Test
 
Enter number of vertices
 
6
 
Enter matrix
 
0 1 0 0 0 1
0 0 0 0 0 0
1 0 0 1 0 0
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 1 0
 
Transitive closure :
 
    0   1   2   3   4   5
0   *   *       *   *   *
1       *
2   *   *   *   *   *   *
3               *
4               *   *
5               *   *   *

Related posts:

Convert String to Byte Array and Reverse in Java
Java Program to Implement Cubic convergence 1/pi Algorithm
Java Program to Implement CopyOnWriteArrayList API
Service Registration with Eureka
Introduction to Java 8 Streams
Spring Boot Security Auto-Configuration
Java Program to Solve any Linear Equations
Làm thế nào tạo instance của một class mà không gọi từ khóa new?
Guide to java.util.concurrent.Future
Spring Boot - Tracing Micro Service Logs
Java Program to Implement LinkedTransferQueue API
Java Program to Solve a Matching Problem for a Given Specific Case
Using the Map.Entry Java Class
Java Program to Find ith Largest Number from a Given List Using Order-Statistic Algorithm
Java Program to Implement Quick Sort Using Randomization
Java Program to Implement vector
Java Program to Check whether Undirected Graph is Connected using DFS
Understanding Memory Leaks in Java
Java Program to Check if it is a Sparse Matrix
Deploy a Spring Boot WAR into a Tomcat Server
Serverless Functions with Spring Cloud Function
Jackson Unmarshalling JSON with Unknown Properties
Java Program to Implement Sorted Array
Hướng dẫn Java Design Pattern – DAO
Java Program to Implement Strassen Algorithm
Java Program to Implement Brent Cycle Algorithm
Java Program to Generate a Random Subset by Coin Flipping
Java Program to Implement Radix Sort
Java Program to Use Above Below Primitive to Test Whether Two Lines Intersect
Java Program to Create a Random Linear Extension for a DAG
Simplify the DAO with Spring and Java Generics
Redirect to Different Pages after Login with Spring Security