In this tutorial, we will learn about the Floyd Warshall algorithm and we will also see the program to implement the Floyd Warshall algorithm using Java.

The Floyd Warshall Algorithm is used to solve the All-Pairs Shortest Path problem i.e., to find the shortest distances between every pair of nodes in a given weighted directed Graph. It works for both the directed and undirected weighted graphs however it does not work for the graphs with edges that have negative weights. To solve the All-Pairs Shortest Path problem, this algorithm uses dynamic programming.

The algorithm uses the following formula to find the shortest path between each pair of nodes:

D^{(k)}[i,j]= min{ D^{(k-1)}[i,j], D^{(k-1)}[i,k]+ D^{(k-1)}[k,j] }

where D^{0} is the weighted matrix of the graph given by the user

k is the intermediate node between i and j.

The time complexity and space complexity of this algorithm is O(n^{3}) (for 3 loops) and O(n^{2}) respectively.

While giving the graph matrix as input, the pair of vertices containing no edges will be marked as infinity and the graph containing self-loop will be marked as zero.

Note: In the code given below 9999 is used in place of infinity

import java.util.Scanner; public class Floyd_Warshall { public static void minDistance (int adj[][],int vertices) { int i, j, count=0; //Here k is acting as an intermediate node while( count < vertices) { for (i = 0; i < vertices; i++) { for (j = 0; j < vertices; j++) { if (adj[i][count] + adj[count][j] < adj[i][j]) adj[i][j] = adj[i][count] + adj[count][j]; } } count++; } display(adj,vertices); } public static void display(int adj[][],int vertices) { System.out.print ("The following matrix shows the shortest distances between every pair of vertices \n"); for (int i = 0; i < vertices; i++) { System.out.print("\t"+(i+1)); } System.out.print("\n"); for (int i = 0; i < vertices; i++) { System.out.print((i+1)+"\t"); for (int j = 0; j < vertices; j++) { System.out.print (adj[i][j]+"\t"); } System.out.print("\n"); } System.out.println("\nNote: If the distance between any two Vertices is 9999 then there is no path between them."); } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); System.out.print("Enter the total number of vertices in the graph: "); int vertices=sc.nextInt(); int adj[][]=new int[vertices][vertices],i,j; for(i=0;i<vertices;i++) { for(j=0;j<vertices;j++) { System.out.print("Enter Adj["+i+"]["+j+"]:"); adj[i][j]=sc.nextInt(); } } minDistance (adj,vertices); } }

The input and output for this code are given below:

Submitted by Abhishek Birendra Verma (AbhishekVerma)

Download packets of source code on Coders Packet

## Comments