Package org.jgrapht.alg
Class FloydWarshallShortestPaths<V,E>
- java.lang.Object
-
- 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
Constructors Constructor Description FloydWarshallShortestPaths(Graph<V,E> graph)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description 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.
-
-
-
Method Detail
-
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 vertexb
- 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 verticeb
- To vertice- Returns:
- the path, or null if none found
-
-