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               *   *   *