public class BreadthFirstDirectedPaths extends Object
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.
Each call to distTo(int)
and hasPathTo(int)
takes constant time;
each call to pathTo(int)
takes time proportional to the length
of the path.
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.
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 . |
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. |
public BreadthFirstDirectedPaths(Digraph G, int s)
s
and every other vertex in graph G
.G
- the digraphs
- the source vertexIllegalArgumentException
- unless 0 <= v < V
public BreadthFirstDirectedPaths(Digraph G, Iterable<Integer> sources)
sources
to every other vertex in graph G
.G
- the digraphsources
- the source verticesIllegalArgumentException
- unless each vertex v
in
sources
satisfies 0 <= v < V
public boolean hasPathTo(int v)
s
(or sources) to vertex v
?v
- the vertextrue
if there is a directed path, false
otherwiseIllegalArgumentException
- unless 0 <= v < V
public int distTo(int v)
s
(or sources) to vertex v
?v
- the vertexIllegalArgumentException
- unless 0 <= v < V
public Iterable<Integer> pathTo(int v)
s
(or sources) to v
, or
null
if no such path.v
- the vertexIllegalArgumentException
- unless 0 <= v < V
public static void main(String[] args)
BreadthFirstDirectedPaths
data type.args
- the command-line arguments