FloydWarshall.java

packagecom.jwetherell.algorithms.graph;

importjava.util.HashMap;
importjava.util.List;
importjava.util.Map;

importcom.jwetherell.algorithms.data_structures.Graph;

/**
 * Floyd–Warshall algorithm is a graph analysis algorithm for finding shortest
 * paths in a weighted graph (with positive or negative edge weights).
 * <p>
 * Worst case: O(V^3)
 * <p>
 * @see <a href="https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm">Floyd-Warshall Algorithm (Wikipedia)</a>
 * <br>
 * @author Justin Wetherell <phishman3579@gmail.com>
 */
publicclassFloydWarshall {

privateFloydWarshall() { }

publicstaticMap<Graph.Vertex<Integer>, Map<Graph.Vertex<Integer>, Integer>> getAllPairsShortestPaths(Graph<Integer> graph) {
if (graph == null)
throw (newNullPointerException("Graph must be non-NULL."));

finalList<Graph.Vertex<Integer>> vertices = graph.getVertices();

finalint[][] sums = newint[vertices.size()][vertices.size()];
for (inti = 0; i < sums.length; i++) {
for (intj = 0; j < sums[i].length; j++) {
sums[i][j] = Integer.MAX_VALUE;
 }
 }

finalList<Graph.Edge<Integer>> edges = graph.getEdges();
for (Graph.Edge<Integer> e : edges) {
finalintindexOfFrom = vertices.indexOf(e.getFromVertex());
finalintindexOfTo = vertices.indexOf(e.getToVertex());
sums[indexOfFrom][indexOfTo] = e.getCost();
 }

for (intk = 0; k < vertices.size(); k++) {
for (inti = 0; i < vertices.size(); i++) {
for (intj = 0; j < vertices.size(); j++) {
if (i == j) {
sums[i][j] = 0;
 } else {
finalintijCost = sums[i][j];
finalintikCost = sums[i][k];
finalintkjCost = sums[k][j];
finalintsummed = (ikCost != Integer.MAX_VALUE && 
kjCost != Integer.MAX_VALUE) ? 
 (ikCost + kjCost)
 : 
Integer.MAX_VALUE;
if (ijCost > summed)
sums[i][j] = summed;
 }
 }
 }
 }

finalMap<Graph.Vertex<Integer>, Map<Graph.Vertex<Integer>, Integer>> allShortestPaths = newHashMap<Graph.Vertex<Integer>, Map<Graph.Vertex<Integer>, Integer>>();
for (inti = 0; i < sums.length; i++) {
for (intj = 0; j < sums[i].length; j++) {
finalGraph.Vertex<Integer> from = vertices.get(i);
finalGraph.Vertex<Integer> to = vertices.get(j);

Map<Graph.Vertex<Integer>, Integer> map = allShortestPaths.get(from);
if (map == null)
map = newHashMap<Graph.Vertex<Integer>, Integer>();

finalintcost = sums[i][j];
if (cost != Integer.MAX_VALUE)
map.put(to, cost);
allShortestPaths.put(from, map);
 }
 }
returnallShortestPaths;
 }
}