Package edu.princeton.cs.algs4

Class FloydWarshall

  • public class FloydWarshall
extends 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 Θ(V3) time, where V is the number of vertices. Each instance method takes Θ(1) time. It uses Θ(V2) extra space (not including the edge-weighted digraph).

    This correctly computes shortest paths if all arithmetic performed is without floating-point rounding error or arithmetic overflow. This is the case if all edge weights are integers and if none of the intermediate results exceeds 252. Since all intermediate results are sums of edge weights, they are bounded by V C, where V is the number of vertices and C is the maximum absolute value of any edge weight.

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

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Detail

      • FloydWarshall

        public FloydWarshall​(AdjMatrixEdgeWeightedDigraph G)
        Computes a shortest paths tree from each vertex 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

    • Method Detail

      • hasNegativeCycle

        public boolean hasNegativeCycle()
        Is there a negative cycle?
        Returns:
        true if there is a negative cycle, and false otherwise

      • negativeCycle

        public Iterable<DirectedEdge> negativeCycle()
        Returns a negative cycle, or null if there is no such cycle.
        Returns:
        a negative cycle as an iterable of edges, or null if there is no such cycle

      • hasPath

        public boolean hasPath​(int s,
                       int t)
        Is there a path from the vertex s to vertex t?
        Parameters:
        s - the source vertex
        t - the destination vertex
        Returns:
        true if there is a path from vertex s to vertex t, and false otherwise
        Throws:
        IllegalArgumentException - unless 0 <= s < V
        IllegalArgumentException - unless 0 <= t < V

      • 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:
        UnsupportedOperationException - if there is a negative cost cycle
        IllegalArgumentException - unless 0 <= v < V

      • path

        public Iterable<DirectedEdge> 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:
        UnsupportedOperationException - if there is a negative cost cycle
        IllegalArgumentException - unless 0 <= v < V

      • main

        public static void main​(String[] args)
        Unit tests the FloydWarshall data type.
        Parameters:
        args - the command-line arguments