/*
 * (C) Copyright 2009-2017, by Tom Larkworthy and Contributors.
 *
 * JGraphT : a free Java graph-theory library
 *
 * This program and the accompanying materials are dual-licensed under
 * either
 *
 * (a) the terms of the GNU Lesser General Public License version 2.1
 * as published by the Free Software Foundation, or (at your option) any
 * later version.
 *
 * or (per the licensee's choosing)
 *
 * (b) the terms of the Eclipse Public License v1.0 as published by
 * the Eclipse Foundation.
 */
package org.jgrapht.alg.shortestpath;

import java.util.*;

import org.jgrapht.*;
import org.jgrapht.graph.*;
import org.jgrapht.util.*;

/**
 * The Floyd-Warshall algorithm.
 * 
 * 

* The Floyd-Warshall algorithm * finds all shortest paths (all n^2 of them) in O(n^3) time. It can also calculate the graph * diameter. Note that during construction time, no computations are performed! All computations are * performed the first time one of the member methods of this class is invoked. The results are * stored, so all subsequent calls to the same method are computationally efficient. * * @param the graph vertex type * @param the graph edge type * * @author Tom Larkworthy * @author Soren Davidsen (soren@tanesha.net) * @author Joris Kinable * @author Dimitrios Michail */ public class FloydWarshallShortestPaths extends BaseShortestPathAlgorithm { private final List vertices; private final Map vertexIndices; private int nShortestPaths = 0; private double diameter = Double.NaN; private double[][] d = null; private Object[][] backtrace = null; private Object[][] lastHopMatrix = null; /** * Create a new instance of the Floyd-Warshall all-pairs shortest path algorithm. * * @param graph the input graph */ public FloydWarshallShortestPaths(Graph graph) { super(graph); this.vertices = new ArrayList<>(graph.vertexSet()); this.vertexIndices = new HashMap<>(this.vertices.size()); int i = 0; for (V vertex : vertices) { vertexIndices.put(vertex, i++); } } /** * Get the total number of shortest paths. Does not count the paths from a vertex to itself. * * @return total number of shortest paths */ public int getShortestPathsCount() { lazyCalculateMatrix(); return nShortestPaths; } /** * Compute the diameter of the graph. * * @return the diameter (longest of all the shortest paths) computed for the graph. If the graph * contains no vertices, return {@link Double#NaN}. If there is no path between any two * vertices, return {@link Double#POSITIVE_INFINITY}. */ public double getDiameter() { lazyCalculateMatrix(); if (!Double.isNaN(diameter)) { return diameter; } int n = vertices.size(); if (n > 0) { diameter = 0.0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { diameter = Double.max(diameter, d[i][j]); } } } return diameter; } /** * {@inheritDoc} */ @Override public GraphPath getPath(V a, V b) { if (!graph.containsVertex(a)) { throw new IllegalArgumentException("graph must contain the source vertex"); } if (!graph.containsVertex(b)) { throw new IllegalArgumentException("graph must contain the sink vertex"); } lazyCalculateMatrix(); int v_a = vertexIndices.get(a); int v_b = vertexIndices.get(b); if (backtrace[v_a][v_b] == null) { // No path exists return createEmptyPath(a, b); } // Reconstruct the path List edges = new ArrayList<>(); V u = a; while (!u.equals(b)) { int v_u = vertexIndices.get(u); E e = TypeUtil.uncheckedCast(backtrace[v_u][v_b], null); edges.add(e); u = Graphs.getOppositeVertex(graph, e, u); } return new GraphWalk<>(graph, a, b, null, edges, d[v_a][v_b]); } /** * {@inheritDoc} */ @Override public double getPathWeight(V source, V sink) { if (!graph.containsVertex(source)) { throw new IllegalArgumentException("graph must contain the source vertex"); } if (!graph.containsVertex(sink)) { throw new IllegalArgumentException("graph must contain the sink vertex"); } lazyCalculateMatrix(); return d[vertexIndices.get(source)][vertexIndices.get(sink)]; } /** * {@inheritDoc} */ @Override public SingleSourcePaths getPaths(V source) { return new FloydWarshallSingleSourcePaths(source); } /** * Returns the first hop, i.e., the second node on the shortest path from a to b. Lookup time is * O(1). If the shortest path from a to b is a,c,d,e,b, this method returns c. If the next * invocation would query the first hop on the shortest path from c to b, vertex d would be * returned, etc. This method is computationally cheaper than calling * {@link #getPath(Object, Object)} and then reading the first vertex. * * @param a source vertex * @param b target vertex * @return next hop on the shortest path from a to b, or null when there exists no path from a * to b. */ public V getFirstHop(V a, V b) { lazyCalculateMatrix(); int v_a = vertexIndices.get(a); int v_b = vertexIndices.get(b); if (backtrace[v_a][v_b] == null) { // No path exists return null; } else { E e = TypeUtil.uncheckedCast(backtrace[v_a][v_b], null); return Graphs.getOppositeVertex(graph, e, a); } } /** * Returns the last hop, i.e., the second to last node on the shortest path from a to b. Lookup * time is O(1). If the shortest path from a to b is a,c,d,e,b, this method returns e. If the * next invocation would query the next hop on the shortest path from c to e, vertex d would be * returned, etc. This method is computationally cheaper than calling * {@link #getPath(Object, Object)} and then reading the vertex. The first invocation of this * method populates a last hop matrix. * * @param a source vertex * @param b target vertex * @return last hop on the shortest path from a to b, or null when there exists no path from a * to b. */ public V getLastHop(V a, V b) { lazyCalculateMatrix(); int v_a = vertexIndices.get(a); int v_b = vertexIndices.get(b); if (backtrace[v_a][v_b] == null) { // No path exists return null; } else { populateLastHopMatrix(); E e = TypeUtil.uncheckedCast(lastHopMatrix[v_a][v_b], null); return Graphs.getOppositeVertex(graph, e, b); } } /** * Calculates the matrix of all shortest paths, but does not populate the last hops matrix. */ private void lazyCalculateMatrix() { if (d != null) { // already done return; } int n = vertices.size(); // init the backtrace matrix backtrace = new Object[n][n]; // initialize matrix, 0 d = new double[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(d[i], Double.POSITIVE_INFINITY); } // initialize matrix, 1 for (int i = 0; i < n; i++) { d[i][i] = 0.0; } // initialize matrix, 2 if (graph instanceof UndirectedGraph) { for (E edge : graph.edgeSet()) { V source = graph.getEdgeSource(edge); V target = graph.getEdgeTarget(edge); if (!source.equals(target)) { int v_1 = vertexIndices.get(source); int v_2 = vertexIndices.get(target); double edgeWeight = graph.getEdgeWeight(edge); if (Double.compare(edgeWeight, d[v_1][v_2]) < 0) { d[v_1][v_2] = d[v_2][v_1] = edgeWeight; backtrace[v_1][v_2] = edge; backtrace[v_2][v_1] = edge; } } } } else { // This works for both Directed and Mixed graphs! Iterating over // the arcs and querying source/sink does not suffice for graphs // which contain both edges and arcs DirectedGraph directedGraph = (DirectedGraph) graph; for (V v1 : directedGraph.vertexSet()) { int v_1 = vertexIndices.get(v1); for (E e : directedGraph.outgoingEdgesOf(v1)) { V v2 = Graphs.getOppositeVertex(directedGraph, e, v1); if (!v1.equals(v2)) { int v_2 = vertexIndices.get(v2); double edgeWeight = graph.getEdgeWeight(e); if (Double.compare(edgeWeight, d[v_1][v_2]) < 0) { d[v_1][v_2] = edgeWeight; backtrace[v_1][v_2] = e; } } } } } // run fw alg for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { double ik_kj = d[i][k] + d[k][j]; if (Double.compare(ik_kj, d[i][j]) < 0) { d[i][j] = ik_kj; backtrace[i][j] = backtrace[i][k]; } } } } // count shortest paths nShortestPaths = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i != j && Double.isFinite(d[i][j])) { nShortestPaths++; } } } } /** * Populate the last hop matrix, using the earlier computed backtrace matrix. */ private void populateLastHopMatrix() { lazyCalculateMatrix(); if (lastHopMatrix != null) return; // Initialize matrix int n = vertices.size(); lastHopMatrix = new Object[n][n]; // Populate matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j || lastHopMatrix[i][j] != null || backtrace[i][j] == null) continue; // Reconstruct the path from i to j List edges = new ArrayList<>(); V u = vertices.get(i); V b = vertices.get(j); while (!u.equals(b)) { int v_u = vertexIndices.get(u); E e = TypeUtil.uncheckedCast(backtrace[v_u][j], null); edges.add(e); V other = Graphs.getOppositeVertex(graph, e, u); lastHopMatrix[i][vertexIndices.get(other)] = e; u = other; } } } } class FloydWarshallSingleSourcePaths implements SingleSourcePaths { private V source; public FloydWarshallSingleSourcePaths(V source) { this.source = source; } @Override public Graph getGraph() { return graph; } @Override public V getSourceVertex() { return source; } @Override public double getWeight(V sink) { if (!graph.containsVertex(source)) { throw new IllegalArgumentException("graph must contain the source vertex"); } if (!graph.containsVertex(sink)) { throw new IllegalArgumentException("graph must contain the sink vertex"); } lazyCalculateMatrix(); return d[vertexIndices.get(source)][vertexIndices.get(sink)]; } @Override public GraphPath getPath(V sink) { if (!graph.containsVertex(source)) { throw new IllegalArgumentException("graph must contain the source vertex"); } if (!graph.containsVertex(sink)) { throw new IllegalArgumentException("graph must contain the sink vertex"); } lazyCalculateMatrix(); int v_a = vertexIndices.get(source); int v_b = vertexIndices.get(sink); if (backtrace[v_a][v_b] == null) { // No path exists return createEmptyPath(source, sink); } // Reconstruct the path List edges = new ArrayList<>(); V u = source; while (!u.equals(sink)) { int v_u = vertexIndices.get(u); E e = TypeUtil.uncheckedCast(backtrace[v_u][v_b], null); edges.add(e); u = Graphs.getOppositeVertex(graph, e, u); } return new GraphWalk<>(graph, source, sink, null, edges, d[v_a][v_b]); } } }

Ads help maintain this website.