Package edu.princeton.cs.algs4

Class BellmanFordSP

  • public class BellmanFordSP
extends Object
    The BellmanFordSP class represents a data type for solving the single-source 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 from the source vertex s to every other vertex or a negative cycle reachable from the source vertex.

    This implementation uses a queue-based implementation of the Bellman-Ford-Moore algorithm. The constructor takes Θ(E V) time in the worst case, where V is the number of vertices and E is the number of edges. In practice, it performs much better. Each instance method takes Θ(1) time. It uses Θ(V) 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

      • BellmanFordSP

        public BellmanFordSP​(EdgeWeightedDigraph digraph,
                     int s)
        Computes a shortest paths tree from s to every other vertex in the edge-weighted digraph.
        Parameters:
        digraph - the acyclic digraph
        s - the source vertex
        Throws:
        IllegalArgumentException - unless 0 <= s < V

    • Method Detail

      • hasNegativeCycle

        public boolean hasNegativeCycle()
        Is there a negative cycle reachable from the source vertex s?
        Returns:
        true if there is a negative cycle reachable from the source vertex s, and false otherwise

      • negativeCycle

        public Iterable<DirectedEdge> negativeCycle()
        Returns a negative cycle reachable from the source vertex s, or null if there is no such cycle.
        Returns:
        a negative cycle reachable from the source vertex s as an iterable of edges, and null if there is no such cycle

      • distTo

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

      • hasPathTo

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

      • pathTo

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

      • main

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