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

Constructor Summary
FloydWarshallShortestPaths(Graph<V,E> g)
          Constructs the shortest path array for the given graph.
 
Method Summary
 double getDiameter()
           
 double shortestDistance(V v1, V v2)
          Retrieves the shortest distance between two vertices.
 
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> g)
Constructs the shortest path array for the given graph.

Parameters:
g - input graph
Method Detail

shortestDistance

public double shortestDistance(V v1,
                               V v2)
Retrieves the shortest distance between two vertices.

Parameters:
v1 - first vertex
v2 - second vertex
Returns:
distance, or positive infinity if no path

getDiameter

public double getDiameter()
Returns:
diameter computed for the graph