Class FloydWarshallShortestPaths<V,​E>


  • public class FloydWarshallShortestPaths<V,​E>
    extends java.lang.Object
    The Floyd-Warshall algorithm finds all shortest paths (all n^2 of them) in O(n^3) time. This also works out the graph diameter during the process.
    Author:
    Tom Larkworthy, Soren Davidsen
    • Constructor Detail

      • FloydWarshallShortestPaths

        public FloydWarshallShortestPaths​(Graph<V,​E> graph)
    • Method Detail

      • getGraph

        public Graph<V,​E> getGraph()
        Returns:
        the graph on which this algorithm operates
      • getShortestPathsCount

        public int getShortestPathsCount()
        Returns:
        total number of shortest paths
      • shortestDistance

        public double shortestDistance​(V a,
                                       V b)
        Get the length of a shortest path.
        Parameters:
        a - first vertex
        b - second vertex
        Returns:
        shortest distance between a and b
      • getDiameter

        public double getDiameter()
        Returns:
        the diameter (longest of all the shortest paths) computed for the graph
      • getShortestPath

        public GraphPath<V,​E> getShortestPath​(V a,
                                                    V b)
        Get the shortest path between two vertices. Note: The paths are calculated using a recursive algorithm. It *will* give problems on paths longer than the stack allows.
        Parameters:
        a - From vertice
        b - To vertice
        Returns:
        the path, or null if none found
      • getShortestPaths

        public java.util.List<GraphPath<V,​E>> getShortestPaths​(V v)
        Get shortest paths from a vertex to all other vertices in the graph.
        Parameters:
        v - the originating vertex
        Returns:
        List of paths