Floyd Warshall Algorithm in Java

This Java program is to implement the Floyd-Warshall algorithm.The algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles) and also for finding transitive closure of a relation R.

Here is the source code of the Java program to implement Floyd-Warshall algorithm. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

```
import java.util.Scanner;
```
```
 
```
```
public class FloydWarshall
```
```
{
```
```
    private int distancematrix[][];
```
```
    private int numberofvertices;
```

    public static final int INFINITY = 999;

```
 
```

    public FloydWarshall(int numberofvertices)

```
    {
```

        distancematrix = new int[numberofvertices + 1][numberofvertices + 1];

        this.numberofvertices = numberofvertices;

```
    }
```
```
 
```

    public void floydwarshall(int adjacencymatrix[][])

```
    {
```

        for (int source = 1; source <= numberofvertices; source++)

```
        {
```

            for (int destination = 1; destination <= numberofvertices; destination++)

```
            {
```

                distancematrix[source][destination] = adjacencymatrix[source][destination];

```
            }
```
```
        }
```
```
 
```

        for (int intermediate = 1; intermediate <= numberofvertices; intermediate++)

```
        {
```

            for (int source = 1; source <= numberofvertices; source++)

```
            {
```

                for (int destination = 1; destination <= numberofvertices; destination++)

```
                {
```

                    if (distancematrix[source][intermediate] + distancematrix[intermediate][destination]

                         < distancematrix[source][destination])

                        distancematrix[source][destination] = distancematrix[source][intermediate]

                            + distancematrix[intermediate][destination];

```
                }
```
```
            }
```
```
        }
```
```
 
```

        for (int source = 1; source <= numberofvertices; source++)

            System.out.print("\t" + source);

```
 
```
```
        System.out.println();
```

        for (int source = 1; source <= numberofvertices; source++)

```
        {
```

            System.out.print(source + "\t");

            for (int destination = 1; destination <= numberofvertices; destination++)

```
            {
```

                System.out.print(distancematrix[source][destination] + "\t");

```
            }
```
```
            System.out.println();
```
```
        }
```
```
    }
```
```
 
```

    public static void main(String... arg)

```
    {
```
```
        int adjacency_matrix[][];
```
```
        int numberofvertices;
```
```
 
```

        Scanner scan = new Scanner(System.in);

        System.out.println("Enter the number of vertices");

        numberofvertices = scan.nextInt();

```
 
```

        adjacency_matrix = new int[numberofvertices + 1][numberofvertices + 1];

        System.out.println("Enter the Weighted Matrix for the graph");

        for (int source = 1; source <= numberofvertices; source++)

```
        {
```

            for (int destination = 1; destination <= numberofvertices; destination++)

```
            {
```

                adjacency_matrix[source][destination] = scan.nextInt();

                if (source == destination)

```
                {
```

                    adjacency_matrix[source][destination] = 0;

```
                    continue;
```
```
                }
```

                if (adjacency_matrix[source][destination] == 0)

```
                {
```

                    adjacency_matrix[source][destination] = INFINITY;

```
                }
```
```
            }
```
```
        }
```
```
 
```

        System.out.println("The Transitive Closure of the Graph");

        FloydWarshall floydwarshall = new FloydWarshall(numberofvertices);

        floydwarshall.floydwarshall(adjacency_matrix);

```
        scan.close();
```
```
    }
```
```
}
```

$javac FloydWarshall.java
$java FloydWarshall 
 
Enter the number of vertices
4
 
Enter the Weighted Matrix for the graph
0 0 3 0
2 0 0 0 
0 7 0 1
6 0 0 0
 
The Transitive Closure of the Graph
 
	1	2	3	4
1	0	10	3	4	
2	2	0	5	6	
3	7	7	0	1	
4	6	16	9	0

« Prev - Java Program to Implement Dijkstra’s Algorithm using Queue

» Next - Java Program to Implement Bellman Ford Algorithm

Related Posts:

Recommended Articles: