Class 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
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      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