edu.princeton.cs.algs4

• Object

• ```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 time proportional to V + E, where V is the number of vertices and E is the number of edges. It uses extra space (not including the digraph) proportional to V.

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

Author:
Robert Sedgewick, Kevin Wayne
• ### Constructor Summary

Constructors
Constructor and Description
```BreadthFirstDirectedPaths(Digraph G, int s)```
Computes the shortest path from `s` and every other vertex in graph `G`.
```BreadthFirstDirectedPaths(Digraph G, Iterable<Integer> sources)```
Computes the shortest path from any one of the source vertices in `sources` to every other vertex in graph `G`.
• ### Method Summary

Methods
Modifier and Type Method and Description
`int` `distTo(int v)`
Returns the number of edges in a shortest path from the source `s` (or sources) to vertex `v`?
`boolean` `hasPathTo(int v)`
Is there a directed path from the source `s` (or sources) to vertex `v`?
`static void` `main(String[] args)`
Unit tests the `BreadthFirstDirectedPaths` data type.
`Iterable<Integer>` `pathTo(int v)`
Returns a shortest path from `s` (or sources) to `v`, or `null` if no such path.
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

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

```public BreadthFirstDirectedPaths(Digraph G,
Iterable<Integer> sources)```
Computes the shortest path from any one of the source vertices in `sources` to every other vertex in graph `G`.
Parameters:
`G` - the digraph
`sources` - the source vertices
Throws:
`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 a shortest 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