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.

  1. /**
  2.  **  Java Program to Implement Warshall Algorithm
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** Class Warshall **/
  8. public class Warshall
  9. {
  10.     private int V;    
  11.     private boolean[][] tc;
  12.     /** Function to make the transitive closure **/
  13.     public void getTC(int[][] graph)
  14.     {
  15.         this.V = graph.length;
  16.         tc = new boolean[V][V];
  17.         for (int i = 0; i < V; i++) 
  18.         {    
  19.             for (int j = 0; j < V; j++) 
  20.                 if (graph[i][j] != 0)
  21.                     tc[i][j] = true;
  22.             tc[i][i] = true;
  23.         }
  24.         for (int i = 0; i < V; i++) 
  25.         {
  26.             for (int j = 0; j < V; j++) 
  27.             {
  28.                 if (tc[j][i]) 
  29.                     for (int k = 0; k < V; k++) 
  30.                         if (tc[j][i] && tc[i][k]) 
  31.                             tc[j][k] = true;             
  32.             }
  33.         }
  34.     }
  35.     /** Funtion to display the trasitive closure **/
  36.     public void displayTC()
  37.     {
  38.         System.out.println("\nTransitive closure :\n");
  39.         System.out.print(" ");
  40.         for (int v = 0; v < V; v++)
  41.            System.out.print("   " + v );
  42.         System.out.println();
  43.         for (int v = 0; v < V; v++) 
  44.         {
  45.             System.out.print(v +" ");
  46.             for (int w = 0; w < V; w++) 
  47.             {
  48.                 if (tc[v][w]) 
  49.                     System.out.print("  * ");
  50.                 else                  
  51.                     System.out.print("    ");
  52.             }
  53.             System.out.println();
  54.         }
  55.     }    
  56.  
  57.     /** Main function **/
  58.     public static void main (String[] args) 
  59.     {
  60.         Scanner scan = new Scanner(System.in);
  61.         System.out.println("Warshall Algorithm Test\n");
  62.         /** Make an object of Warshall class **/
  63.         Warshall w = new Warshall();
  64.  
  65.         /** Accept number of vertices **/
  66.         System.out.println("Enter number of vertices\n");
  67.         int V = scan.nextInt();
  68.  
  69.         /** get graph **/
  70.         System.out.println("\nEnter matrix\n");
  71.         int[][] graph = new int[V][V];
  72.         for (int i = 0; i < V; i++)
  73.             for (int j = 0; j < V; j++)
  74.                 graph[i][j] = scan.nextInt();
  75.  
  76.         w.getTC(graph);
  77.         w.displayTC();
  78.     }
  79. }

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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.