Programming Geek
Rated 4.7/5 based on 1446 reviews  ### 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)][Integer.parseInt(s)] = Integer.parseInt(s);

}

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]);

}
}
}
}
}
}
```