edu.princeton.cs.algs4

Class BreadthFirstDirectedPaths

java.lang.Object

edu.princeton.cs.algs4.BreadthFirstDirectedPaths

public class BreadthFirstDirectedPaths
extends java.lang.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. 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 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, java.lang.Iterable<java.lang.Integer> sources) Computes the shortest path from any one of the source vertices in sources to every other vertex in graph G.

Method Summary

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(java.lang.String[] args) Unit tests the BreadthFirstDirectedPaths data type.
java.lang.Iterable<java.lang.Integer>	pathTo(int v) Returns a shortest path from s (or sources) to v, or null if no such path.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BreadthFirstDirectedPaths

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:

java.lang.IllegalArgumentException - unless 0 <= v < V

BreadthFirstDirectedPaths

public BreadthFirstDirectedPaths(Digraph G,
                                 java.lang.Iterable<java.lang.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:

java.lang.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:

java.lang.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:

java.lang.IllegalArgumentException - unless 0 <= v < V

pathTo

public java.lang.Iterable<java.lang.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:

java.lang.IllegalArgumentException - unless 0 <= v < V

main

public static void main(java.lang.String[] args)

Unit tests the BreadthFirstDirectedPaths data type.

Parameters:

args - the command-line arguments