Java Program to Find Shortest Path using Floyd-Warshall’s Algorithm

This is a java program to find shortest path between all vertices using FLoyd-Warshall’s algorithm. In computer science, the Floyd–Warshall algorithm (also known as Floyd’s algorithm, Roy–Warshall algorithm, Roy–Floyd algorithm, or the WFI 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, see below) and also for finding transitive closure of a relation R. A single execution of the algorithm will find the lengths (summed weights) of the shortest paths between all pairs of vertices, though it does not return details of the paths themselves.

Here is the source code of the Java Program to Find Shortest Path Between All Vertices Using Floyd-Warshall’s Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. package com.sanfoundry.graph;
  3.  
  4. import java.util.Scanner;
  5.  
  6. public class FloydWarshallShortestPath
  7. {
  8.     private int             distancematrix[][];
  9.     private int             numberofvertices;
  10.     public static final int INFINITY = 999;
  11.  
  12.     public FloydWarshallShortestPath(int numberofvertices)
  13.     {
  14.         distancematrix = new int[numberofvertices + 1][numberofvertices + 1];
  15.         this.numberofvertices = numberofvertices;
  16.     }
  17.  
  18.     public void floydwarshall(int adjacencymatrix[][])
  19.     {
  20.         for (int source = 1; source <= numberofvertices; source++)
  21.         {
  22.             for (int destination = 1; destination <= numberofvertices; destination++)
  23.             {
  24.                 distancematrix[source][destination] = adjacencymatrix[source][destination];
  25.             }
  26.         }
  27.         for (int intermediate = 1; intermediate <= numberofvertices; intermediate++)
  28.         {
  29.             for (int source = 1; source <= numberofvertices; source++)
  30.             {
  31.                 for (int destination = 1; destination <= numberofvertices; destination++)
  32.                 {
  33.                     if (distancematrix[source][intermediate]
  34.                             + distancematrix[intermediate][destination] < distancematrix[source][destination])
  35.                         distancematrix[source][destination] = distancematrix[source][intermediate]
  36.                                 + distancematrix[intermediate][destination];
  37.                 }
  38.             }
  39.         }
  40.         for (int source = 1; source <= numberofvertices; source++)
  41.             System.out.print("\t" + source);
  42.         System.out.println();
  43.         for (int source = 1; source <= numberofvertices; source++)
  44.         {
  45.             System.out.print(source + "\t");
  46.             for (int destination = 1; destination <= numberofvertices; destination++)
  47.             {
  48.                 System.out.print(distancematrix[source][destination] + "\t");
  49.             }
  50.             System.out.println();
  51.         }
  52.     }
  53.  
  54.     public static void main(String... arg)
  55.     {
  56.         int adjacency_matrix[][];
  57.         int numberofvertices;
  58.         Scanner scan = new Scanner(System.in);
  59.         System.out.println("Enter the number of vertices");
  60.         numberofvertices = scan.nextInt();
  61.         adjacency_matrix = new int[numberofvertices + 1][numberofvertices + 1];
  62.         System.out.println("Enter the Weighted Matrix for the graph");
  63.         for (int source = 1; source <= numberofvertices; source++)
  64.         {
  65.             for (int destination = 1; destination <= numberofvertices; destination++)
  66.             {
  67.                 adjacency_matrix[source][destination] = scan.nextInt();
  68.                 if (source == destination)
  69.                 {
  70.                     adjacency_matrix[source][destination] = 0;
  71.                     continue;
  72.                 }
  73.                 if (adjacency_matrix[source][destination] == 0)
  74.                 {
  75.                     adjacency_matrix[source][destination] = INFINITY;
  76.                 }
  77.             }
  78.         }
  79.         System.out.println("The Transitive Closure of the Graph");
  80.         FloydWarshallShortestPath floydwarshall = new FloydWarshallShortestPath(
  81.                 numberofvertices);
  82.         floydwarshall.floydwarshall(adjacency_matrix);
  83.         scan.close();
  84.     }
  85. }

Output:

$ javac FloydWarshallShortestPath.java
$ java FloydWarshallShortestPath
 
Enter the number of vertices
6
Enter the Weighted Matrix for the graph
0 4 0 0 1 0
0 0 1 0 2 0
0 0 0 0 0 0 
0 0 0 0 0 0
0 0 0 5 0 3
0 0 0 0 0 0
The Transitive Closure of the Graph (999 represents not reachable)
	1	2	3	4	5	6
1	0	4	5	6	1	4	
2	999	0	1	7	2	5	
3	999	999	0	999	999	999	
4	999	999	999	0	999	999	
5	999	999	999	5	0	3	
6	999	999	999	999	999	0

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.