Package com.macrofocus.molap.network

Class FloydWarshall<Node,​Link>

  • public class FloydWarshall<Node,​Link>
extends java.lang.Object
    The FloydWarshall class represents a data type for solving the all-pairs shortest paths problem in edge-weighted digraphs with no negative cycles. The edge weights can be positive, negative, or zero. This class finds either a shortest path between every pair of vertices or a negative cycle.

    This implementation uses the Floyd-Warshall algorithm. The constructor takes time proportional to V3 in the worst case, where V is the number of vertices. Afterwards, the dist(), hasPath(), and hasNegativeCycle() methods take constant time; the path() and negativeCycle() method takes time proportional to the number of edges returned.

    For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    • Constructor Summary

      Constructors 
      Constructor Description
      FloydWarshall​(Network<Node,​Link,​?,​?> G)
      Computes a shortest paths tree from each vertex to to every other vertex in the edge-weighted digraph G.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      double dist​(int s, int t)
      Returns the length of a shortest path from vertex s to vertex t.
      Matrix getDistanceMatrix()  
      Matrix getNodeDistanceMatrix()  
      java.lang.Iterable<Link> path​(int s, int t)
      Returns a shortest path from vertex s to vertex t.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • FloydWarshall

        public FloydWarshall​(Network<Node,​Link,​?,​?> G)
        Computes a shortest paths tree from each vertex to to every other vertex in the edge-weighted digraph G. If no such shortest path exists for some pair of vertices, it computes a negative cycle.
        Parameters:
        G - the edge-weighted digraph Starting Floyd-Warshall algorithm on network with 1005 vertices x 3808 edges (dwt_1005.vna) Completed Floyd-Warshall algorithm in 1478 ms Starting Floyd-Warshall algorithm on network with 2000 vertices x 9912 edges (block_2000.vna) Initialized distance matrix in 32 ms Initialized distances using edge-weighted digraph's 6 ms Floyd-Warshall updates completed in 18973 ms Completed Floyd-Warshall algorithm in 19012 ms Starting Floyd-Warshall algorithm on network with 2050 vertices x 6144 edges (sierpinski3d.vna) Initialized distance matrix in 59 ms Initialized distances using edge-weighted digraph's 5 ms Floyd-Warshall updates completed in 2041 ms Completed Floyd-Warshall algorithm in 2105 ms Starting Floyd-Warshall algorithm on network with 4720 vertices x 13722 egets (3elt.vna) Completed Floyd-Warshall algorithm in 140730 ms Starting Floyd-Warshall algorithm on network with 4941 vertices x 6594 edges (us_powergrid.vna) Completed Floyd-Warshall algorithm in 90981 ms Starting Floyd-Warshall algorithm on network with 2353 vertices (BSF Employed persons by commune of residence and work) Initialized distance matrix in 89 ms Initialized distances using edge-weighted digraph's 25 ms Floyd-Warshall updates completed in 42536 ms Completed Floyd-Warshall algorithm in 42650 ms

    • Method Detail

      • getDistanceMatrix

        public Matrix getDistanceMatrix()

      • getNodeDistanceMatrix

        public Matrix getNodeDistanceMatrix()

      • dist

        public double dist​(int s,
                   int t)
        Returns the length of a shortest path from vertex s to vertex t.
        Parameters:
        s - the source vertex
        t - the destination vertex
        Returns:
        the length of a shortest path from vertex s to vertex t; Double.POSITIVE_INFINITY if no such path
        Throws:
        java.lang.UnsupportedOperationException - if there is a negative cost cycle
        java.lang.IllegalArgumentException - unless 0 <= v < V

      • path

        public java.lang.Iterable<Link> path​(int s,
                                     int t)
        Returns a shortest path from vertex s to vertex t.
        Parameters:
        s - the source vertex
        t - the destination vertex
        Returns:
        a shortest path from vertex s to vertex t as an iterable of edges, and null if no such path
        Throws:
        java.lang.UnsupportedOperationException - if there is a negative cost cycle
        java.lang.IllegalArgumentException - unless 0 <= v < V