Package org.jgrapht.alg
Class FloydWarshallShortestPaths<V,E>
java.lang.Object
org.jgrapht.alg.FloydWarshallShortestPaths<V,E>
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
-
Constructor Summary
ConstructorsConstructorDescriptionConstructs the shortest path array for the given graph. -
Method Summary
Modifier and TypeMethodDescriptiondouble
double
shortestDistance
(V v1, V v2) Retrieves the shortest distance between two vertices.
-
Constructor Details
-
FloydWarshallShortestPaths
Constructs the shortest path array for the given graph.- Parameters:
g
- input graph
-
-
Method Details
-
shortestDistance
Retrieves the shortest distance between two vertices.- Parameters:
v1
- first vertexv2
- second vertex- Returns:
- distance, or positive infinity if no path
-
getDiameter
public double getDiameter()- Returns:
- diameter computed for the graph
-