jTruBela

Floyd Warshall Algorithm

Dec 5th, 2021 (edited)
955
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package allPairsShortestPath;
  2.  
  3. public class Graph4 {
  4.     int n=5;
  5.     static int[][] matrix;
  6.     int[][] A;
  7.     int[] d;
  8.    
  9.     public Graph4 () {
  10.     }
  11.    
  12.     public Graph4 (int _n, int[][] _A) {
  13.         n = _n;
  14.         A = _A;
  15.     }
  16.  
  17.     public void floyd_warshall (int graph[][]) {
  18.         matrix = new int[n][n];
  19.         initialize_Graph(graph);
  20.        
  21.         for (int k = 0; k < n; k++) {
  22.             for (int i = 0; i < n; i++) {
  23.                 for (int j = 0; j < n; j++) {
  24.                     min(k, i, j);
  25.                 }
  26.             }
  27.         }
  28.         display_matrix(matrix);
  29.     }
  30.    
  31.     public int[][] initialize_Graph(int [][]A) {
  32.         for(int i=0; i < n;i++) {
  33.             // for each edge weight in the given graph
  34.             for(int j=0; j< n;j++)
  35.             {
  36.             //update the adjacency matrix weight
  37.             matrix[i][j] = A[i][j];
  38.             }
  39.         }
  40.         return matrix;
  41.     }
  42.    
  43.     public void min (int i, int j, int k) {
  44.         //if current edge weight + alternate edge weight is < the initial weight
  45.         if(matrix[j][i] + matrix[i][k] < matrix[j][k]) {
  46.             //update initial weight with lesser weight
  47.             matrix[j][k] = matrix[j][i] + matrix[i][k];
  48.         }
  49.     }
  50.  
  51.     public void display_matrix(int[][] matrix) {       
  52.         for (int i = 0; i < n; i++) {
  53.             for (int j = 0; j < n; j++) {
  54.                 System.out.print(" " + matrix[i][j] + " ");
  55.             }
  56.             System.out.println();
  57.         }
  58.     }
  59.    
  60.     public static void main(String[] args) {
  61.         // TODO Auto-generated method stub
  62.         int F = 1_072_999_999;  //Integer.MAX wouldn't allow it to update..
  63.                                 //not sure what to do so i just chose the biggest number it would accept lol
  64.         int[][] A = {
  65.         {0, 3, 8, F, -4},
  66.         {F, 0, F, 1, 7},
  67.         {F, 4, 0, F, F},
  68.         {2, F, -5, 0, F},
  69.         {F, F, F, 6, 0}
  70.         };
  71.        
  72.         System.out.println("The pairwise shortest distance as a matrix for the given graph is:");
  73.         Graph4 g1 = new Graph4();
  74.         g1.floyd_warshall(A);
  75.  
  76.     }
  77.  
  78. }
RAW Paste Data