Package org.jgrapht.alg

Class FloydWarshallShortestPaths<V,E>

java.lang.Object
org.jgrapht.alg.FloydWarshallShortestPaths<V,E>
public class FloydWarshallShortestPaths<V,E> extends 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 invalid input: '<'soren@tanesha.net>

  • Constructor Details

    • FloydWarshallShortestPaths

      public FloydWarshallShortestPaths(Graph<V,E> graph)

  • Method Details

    • 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 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