Floyd Warshall Algorithm

In computer science, the Floyd – Warshall algorithm (also known as Floyd's algorithm, the Roy – Warshall algorithm, the Roy – Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).A individual execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices.
package DataStructures.Graphs;

import java.util.Arrays;
import java.util.Scanner;

public class FloydWarshall {
    private int DistanceMatrix[][];
    private int numberofvertices;//number of vertices in the graph
    public static final int INFINITY = 999;

    public FloydWarshall(int numberofvertices) {
        DistanceMatrix = new int[numberofvertices + 1][numberofvertices + 1];//stores the value of distance from all the possible path form the source vertex to destination vertex
        Arrays.fill(DistanceMatrix, 0);
        this.numberofvertices = numberofvertices;
    }

    public void floydwarshall(int AdjacencyMatrix[][])//calculates all the distances from source to destination vertex
    {
        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])
                    // if the new distance calculated is less then the earlier shortest
                        // calculated distance it get replaced as new shortest distance
                    {
                        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) {
        Scanner scan = new Scanner(System.in);
        System.out.println("Enter the number of vertices");
        int numberOfVertices = scan.nextInt();
        int[][] adjacencyMatrix = 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++) {
                adjacencyMatrix[source][destination] = scan.nextInt();
                if (source == destination) {
                    adjacencyMatrix[source][destination] = 0;
                    continue;
                }
                if (adjacencyMatrix[source][destination] == 0) {
                    adjacencyMatrix[source][destination] = INFINITY;
                }
            }
        }
        System.out.println("The Transitive Closure of the Graph");
        FloydWarshall floydwarshall = new FloydWarshall(numberOfVertices);
        floydwarshall.floydwarshall(adjacencyMatrix);
        scan.close();
    }
}

LANGUAGE:

DARK MODE: