@@ -0,0 +1,1759 @@
+import java.util.HashMap;%0A%0A/*%0A * The Floyd-Warshall algorithm is used to find the shortest path between%0A * any pair of nodes in a weighted graph with either positive or negative edge%0A * weights but without negative edge cycles.%0A * %0A * The running time of the algorithm is O(n%5E3), being n the number of nodes in%0A * the graph.%0A */%0A%0Apublic class FloydWarshall %7B%0A%0A%09static HashMap%3CInteger, HashMap%3CInteger, Integer%3E%3E adjacencyList = new HashMap%3CInteger, HashMap%3CInteger, Integer%3E%3E();%0A%09static boolean hasNegativeCycle;%0A%0A%09// utility function to add edges to the adjacencyList%0A%09static void addOrUpdateEdge(int from, int to, int weight) %7B%0A%09%09if (adjacencyList.containsKey(from)) %7B%0A%09%09%09adjacencyList.get(from).put(to, weight);%0A%09%09%7D else %7B%0A%09%09%09HashMap%3CInteger, Integer%3E edges = new HashMap%3CInteger, Integer%3E();%0A%09%09%09edges.put(to, weight);%0A%09%09%09adjacencyList.put(from, edges);%0A%09%09%7D%0A%09%7D%0A%0A%09// all-pairs shortest path%0A%09static double%5B%5D%5B%5D floydWarshall(int n) %7B%0A%09%09double%5B%5D%5B%5D distances = new double%5Bn%5D%5Bn%5D;%0A%0A%09%09// initialize the distances matrix from the adjacencyList%0A%09%09for (int i = 0; i %3C n; i++) %7B%0A%09%09%09for (int j = 0; j %3C n; j++) %7B%0A%09%09%09%09if (i == j) %7B%0A%09%09%09%09%09distances%5Bi%5D%5Bj%5D = 0;%0A%09%09%09%09%7D else %7B%0A%09%09%09%09%09if (adjacencyList.containsKey(i)) %7B%0A%09%09%09%09%09%09if (adjacencyList.get(i).containsKey(j)) %7B%0A%09%09%09%09%09%09%09distances%5Bi%5D%5Bj%5D = adjacencyList.get(i).get(j);%0A%09%09%09%09%09%09%7D else %7B%0A%09%09%09%09%09%09%09distances%5Bi%5D%5Bj%5D = Double.POSITIVE_INFINITY;%0A%09%09%09%09%09%09%7D%0A%09%09%09%09%09%7D else %7B%0A%09%09%09%09%09%09distances%5Bi%5D%5Bj%5D = Double.POSITIVE_INFINITY;%0A%09%09%09%09%09%7D%0A%09%09%09%09%7D%0A%09%09%09%7D%0A%09%09%7D%0A%0A%09%09for (int k = 0; k %3C n; k++) %7B%0A%09%09%09for (int i = 0; i %3C n; i++) %7B%0A%09%09%09%09for (int j = 0; j %3C n; j++) %7B%0A%09%09%09%09%09distances%5Bi%5D%5Bj%5D = Math.min(distances%5Bi%5D%5Bj%5D, distances%5Bi%5D%5Bk%5D + distances%5Bk%5D%5Bj%5D);%0A%09%09%09%09%7D%0A%09%09%09%7D%0A%0A%09%09%09if (distances%5Bk%5D%5Bk%5D %3C 0.0) %7B%0A%09%09%09%09hasNegativeCycle = true;%0A%09%09%09%7D%0A%09%09%7D%0A%0A%09%09return distances;%0A%09%7D%0A%0A%7D%0A

Add Floyd Warshall