Floyd Warshall

Floyd Warshall

  August 08, 2017    

---

This is a problem to find shortest path between all pair of vertices

Here we take a vertex as intermediate vertex and check if the path from intermediate  vertex to destination + source vertex to intermediate  is smaller than its given path in input / previous path.

Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class hackerranksolutionc
 {
     public static void floyd(int arr[][],int n)
     {
         int dist[][]=new int[n][n];
//copy old values
         for(int i=0;i<n;i++)
   for(int j=0;j<n;j++)
   dist[i][j]=arr[i][j];

//check with k as intermediate 
   for(int k=0;k<n;k++)
   {
       for(int i=0;i<n;i++)
       {
           for(int j=0;j<n;j++)
           {
               dist[i][j]=Math.min(dist[i][j],dist[i][k]+dist[k][j]);
           }
       }
   }
   for(int i=0;i<n;i++)
   for(int j=0;j<n;j++)
   System.out.print(dist[i][j]+" ");
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   int n=ab.nextInt();
   int arr[][]=new int[n][n];
   for(int i=0;i<n;i++)
   for(int j=0;j<n;j++)
   arr[i][j]=ab.nextInt();
   floyd(arr,n);
   System.out.println();
}
}
}