fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. class FloydWarshell
  4. {
  5.     // Recursive Function to print path of given
  6.     // vertex u from source vertex v
  7.     private static void printPath(int[][] path, int v, int u)
  8.     {
  9.         if (path[v][u] == v)
  10.             return;
  11.  
  12.         printPath(path, v, path[v][u]);
  13.         System.out.print(path[v][u] + " ");
  14.     }
  15.  
  16.     // Function to print the shortest cost with path
  17.     // information between all pairs of vertices
  18.     private static void printSolution(int[][] cost, int[][] path, int N)
  19.     {
  20.         for (int v = 0; v < N; v++)
  21.         {
  22.             for (int u = 0; u < N; u++)
  23.             {
  24.                 if (u != v && path[v][u] != -1)
  25.                 {
  26.                     System.out.print("Shortest Path from vertex " + v +
  27.                             " to vertex " + u + " is (" + v + " ");
  28.                     printPath(path, v, u);
  29.                     System.out.println(u + ")");
  30.                 }
  31.             }
  32.         }
  33.     }
  34.  
  35.     // Function to run Floyd-Warshell algorithm
  36.     public static void FloydWarshell(int[][] adjMatrix, int N)
  37.     {
  38.         // cost[] and parent[] stores shortest-path
  39.         // (shortest-cost/shortest route) information
  40.         int[][] cost = new int[N][N];
  41.         int[][] path = new int[N][N];
  42.  
  43.         // initialize cost[] and parent[]
  44.         for (int v = 0; v < N; v++)
  45.         {
  46.             for (int u = 0; u < N; u++)
  47.             {
  48.                 // initally cost would be same as weight
  49.                 // of the edge
  50.                 cost[v][u] = adjMatrix[v][u];
  51.  
  52.                 if (v == u)
  53.                     path[v][u] = 0;
  54.                 else if (cost[v][u] != Integer.MAX_VALUE)
  55.                     path[v][u] = v;
  56.                 else
  57.                     path[v][u] = -1;
  58.             }
  59.         }
  60.  
  61.         // run Floyd-Warshell
  62.         for (int k = 0; k < N; k++)
  63.         {
  64.             for (int v = 0; v < N; v++)
  65.             {
  66.                 for (int u = 0; u < N; u++)
  67.                 {
  68.                     // If vertex k is on the shortest path from v to u,
  69.                     // then update the value of cost[v][u], path[v][u]
  70.  
  71.                     if (cost[v][k] != Integer.MAX_VALUE
  72.                             && cost[k][u] != Integer.MAX_VALUE
  73.                             && (cost[v][k] + cost[k][u] < cost[v][u]))
  74.                     {
  75.                         cost[v][u] = cost[v][k] + cost[k][u];
  76.                         path[v][u] = path[k][u];
  77.                     }
  78.                 }
  79.  
  80.                 // if diagonal elements become negative, the
  81.                 // graph contains a negative weight cycle
  82.                 if (cost[v][v] < 0)
  83.                 {
  84.                     System.out.println("Negative Weight Cycle Found!!");
  85.                     return;
  86.                 }
  87.             }
  88.         }
  89.  
  90.         // Print the shortest path between all pairs of vertices
  91.         printSolution(cost, path, N);
  92.     }
  93.  
  94.     public static void main(String[] args)
  95.     {
  96.         // Number of vertices in the adjMatrix
  97.         final int N = 4;
  98.         int M = Integer.MAX_VALUE;
  99.  
  100.         // given adjacency representation of matrix
  101.         int[][] adjMatrix = new int[][]
  102.         {
  103.             { 0,  M, -2, M },
  104.             { 4,  0,  3, M },
  105.             { M,  M,  0, 2 },
  106.             { M, -1,  M, 0 }
  107.         };
  108.  
  109.         // Run Floyd Warshell algorithm
  110.         FloydWarshell(adjMatrix, N);
  111.     }
  112. }
Success #stdin #stdout 0.1s 27720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Shortest Path from vertex 0 to vertex 1 is (0 2 3 1)
Shortest Path from vertex 0 to vertex 2 is (0 2)
Shortest Path from vertex 0 to vertex 3 is (0 2 3)
Shortest Path from vertex 1 to vertex 0 is (1 0)
Shortest Path from vertex 1 to vertex 2 is (1 0 2)
Shortest Path from vertex 1 to vertex 3 is (1 0 2 3)
Shortest Path from vertex 2 to vertex 0 is (2 3 1 0)
Shortest Path from vertex 2 to vertex 1 is (2 3 1)
Shortest Path from vertex 2 to vertex 3 is (2 3)
Shortest Path from vertex 3 to vertex 0 is (3 1 0)
Shortest Path from vertex 3 to vertex 1 is (3 1)
Shortest Path from vertex 3 to vertex 2 is (3 1 0 2)
https://ideone.com/JvYScz
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!