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:

Java Program to Implement Sieve Of Eratosthenes
Java Program to Implement ConcurrentSkipListMap API
Introduction to Eclipse Collections
Converting Between a List and a Set in Java
Java Program to Find the Vertex Connectivity of a Graph
Spring REST API + OAuth2 + Angular
Add Multiple Items to an Java ArrayList
Java – InputStream to Reader
Logout in an OAuth Secured Application
Giới thiệu Swagger – Công cụ document cho RESTfull APIs
Circular Dependencies in Spring
So sánh HashSet, LinkedHashSet và TreeSet trong Java
Java Program to Implement Nth Root Algorithm
So sánh HashMap và Hashtable trong Java
Spring Boot - Rest Template
How to Get All Dates Between Two Dates?
Reactive Flow with MongoDB, Kotlin, and Spring WebFlux
Java Program to Check whether Directed Graph is Connected using BFS
Java Program to Create a Random Graph Using Random Edge Generation
Tránh lỗi NullPointerException trong Java như thế nào?
Spring Boot - Admin Server
Introduction to the Functional Web Framework in Spring 5
A Quick JUnit vs TestNG Comparison
Hướng dẫn Java Design Pattern – Service Locator
Java Program to Remove the Edges in a Given Cyclic Graph such that its Linear Extension can be Found
Java Program to Implement Bresenham Line Algorithm
Phương thức tham chiếu trong Java 8 – Method References
Lớp lồng nhau trong java (Java inner class)
Java Program to do a Depth First Search/Traversal on a graph non-recursively
Convert Hex to ASCII in Java
Từ khóa static và final trong java
Spring Boot - Zuul Proxy Server and Routing