Package edu.princeton.cs.algs4

Class BreadthFirstDirectedPaths

  • public class BreadthFirstDirectedPaths
extends Object
    The BreadthDirectedFirstPaths class represents a data type for finding shortest paths (number of edges) from a source vertex s (or set of source vertices) to every other vertex in the digraph.

    This implementation uses breadth-first search. The constructor takes Θ(V + E) time in the worst case, where V is the number of vertices and E is the number of edges. Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the digraph).

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

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Detail

      • BreadthFirstDirectedPaths

        public BreadthFirstDirectedPaths​(Digraph digraph,
                                 int s)
        Computes the shortest path from s and every other vertex in digraph.
        Parameters:
        digraph - the digraph
        s - the source vertex
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • BreadthFirstDirectedPaths

        public BreadthFirstDirectedPaths​(Digraph digraph,
                                 Iterable<Integer> sources)
        Computes the shortest path from any one of the source vertices in sources to every other vertex in digraph.
        Parameters:
        digraph - the digraph
        sources - the source vertices
        Throws:
        IllegalArgumentException - if sources is null
        IllegalArgumentException - if sources contains no vertices
        IllegalArgumentException - unless each vertex v in sources satisfies 0 <= v < V

    • Method Detail

      • hasPathTo

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

      • distTo

        public int distTo​(int v)
        Returns the number of edges in a shortest path from the source s (or sources) to vertex v?
        Parameters:
        v - the vertex
        Returns:
        the number of edges in such a shortest path (or Integer.MAX_VALUE if there is no such path)
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • pathTo

        public Iterable<Integer> pathTo​(int v)
        Returns a shortest path from s (or sources) to v, or null if no such path.
        Parameters:
        v - the vertex
        Returns:
        the sequence of vertices on a shortest path, as an Iterable
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • main

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