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:

Connect through a Proxy
Tạo ứng dụng Java RESTful Client không sử dụng 3rd party libraries
Number Formatting in Java
Java Program to Generate a Graph for a Given Fixed Degree Sequence
Java Program to Implement Johnson’s Algorithm
Java Program to Permute All Letters of an Input String
Getting Started with Forms in Spring MVC
Exploring the Spring 5 WebFlux URL Matching
Java Program to Implement the RSA Algorithm
Java Program to Show the Duality Transformation of Line and Point
Java Program to Check Whether a Directed Graph Contains a Eulerian Path
Java Program to Generate Random Numbers Using Middle Square Method
Mapping Nested Values with Jackson
Jackson – Marshall String to JsonNode
Java Program to Solve Travelling Salesman Problem for Unweighted Graph
Map Serialization and Deserialization with Jackson
Java Program to Implement Stack using Linked List
Spring Boot - Application Properties
Ignore Null Fields with Jackson
Checked and Unchecked Exceptions in Java
Serve Static Resources with Spring
Hướng dẫn sử dụng Lớp FilePermission trong java
Spring Boot - Unit Test Cases
So sánh HashSet, LinkedHashSet và TreeSet trong Java
Java Program to Implement PriorityQueue API
Custom HTTP Header with the HttpClient
Shuffling Collections In Java
Java Program to Perform Partition of an Integer in All Possible Ways
Query Entities by Dates and Times with Spring Data JPA
Sao chép các phần tử của một mảng sang mảng khác như thế nào?
Hướng dẫn Java Design Pattern – Service Locator
Java Program to Perform Quick Sort on Large Number of Elements