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 Θ(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.
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
- if sources
is null
IllegalArgumentException
- 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 vertexInteger.MAX_VALUE
if there is no such path)IllegalArgumentException
- 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