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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

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

« Prev - Java Program to Implement Tarjan Algorithm

» Next - Longest Arithmetic Progression Algorithm in Java

Related Posts:

Recommended Articles: