org.jgrapht.alg
Class FloydWarshallShortestPaths<V,E>

java.lang.Object
  extended by org.jgrapht.alg.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 Summary
FloydWarshallShortestPaths(Graph<V,E> graph)
           
 
Method Summary
 double getDiameter()
           
 Graph<V,E> getGraph()
           
 GraphPath<V,E> getShortestPath(V a, V b)
          Get the shortest path between two vertices.
 java.util.List<GraphPath<V,E>> getShortestPaths(V v)
          Get shortest paths from a vertex to all other vertices in the graph.
 int getShortestPathsCount()
           
 double shortestDistance(V a, V b)
          Get the length of a shortest path.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

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