Dynamic Programming : Floyd Warshall Algorithm

Floyd Warshall Algorithm computes shortest distances between all pair of vertices of a directed graph. It can be used to find shortest path as well by simply keeping track of intermediate vertices. This algorithm is a dynamic programming algorithm and exhibits both optimal substructure and overlapping sub-problems.

Input    :  input is a directed weighted graph.
Output : Shortest distance between pair of vertices.

It tries to find out the shortest distance between the vertices by inserting intermediate vertex that can lead to optimal solution i.e if u ,v and w are three vertices and we have shortest distance between u & w and w & v and the distance between u and v is greater than that of uw and wv than going to v from u via w can be beneficial.

Following program implements the same algorithm:

import java.util.Scanner;

/**
 *
 * @author VIKKU
 */
public class FloydWarshall {

    static int[][] cost;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int vertices, edges;

        System.out.println("Enter number of verices: ");
        vertices = Integer.parseInt(sc.nextLine());

        System.out.println("Enter number of edges: ");
        edges = Integer.parseInt(sc.nextLine());

        cost = new int[vertices][vertices];

        init(cost);

        System.out.println("Enter " + edges + " edges and cost :");

        for (int i = 1; i <= edges; i++) {

            String[] s = sc.nextLine().trim().split(" ");
            cost[Integer.parseInt(s[0])][Integer.parseInt(s[1])] = Integer.parseInt(s[2]);

        }

        floydwarshall(cost);

        System.out.println("Shortest distances are :");

        for (int from = 0; from < cost.length; from++) {

            System.out.println("");

            for (int to = 0; to < cost.length; to++) {

                System.out.print(cost[from][to] + "\t");

            }
        }
    }

    public static void init(int[][] cost) {

        for (int from = 0; from < cost.length; from++) {

            for (int to = 0; to < cost.length; to++) {

                if (from != to) {

                    cost[from][to] = 999999999;

                }
            }
        }
    }

    public static void floydwarshall(int[][] cost) {

        for (int from = 0; from < cost.length; from++) {

            for (int to = 0; to < cost.length; to++) {

                for (int via = 0; via < cost.length; via++) {

                    if (cost[from][to] > (cost[from][via] + cost[via][to])) {

                        cost[from][to] = (cost[from][via] + cost[via][to]);

                    }
                }
            }
        }
    }
}