Class BreadthFirstPaths

java.lang.Object

BreadthFirstPaths

public class BreadthFirstPaths
extends java.lang.Object

The BreadthFirstPaths class represents a data type for finding shortest paths (number of edges) from a source vertex s (or a set of source vertices) to every other vertex in an undirected graph.

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.

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

Constructor Summary

Constructors

Constructor and Description
BreadthFirstPaths(Graph G, int s) Computes the shortest path between s and every other vertex in graph G.
BreadthFirstPaths(Graph G, java.lang.Iterable<java.lang.Integer> sources) Computes the shortest path between any one of the source vertices in sources and 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 between the source s (or sources) and vertex v?
boolean	hasPathTo(int v) Is there a path between the source s (or sources) and vertex v?
static void	main(java.lang.String[] args) Unit tests the BreadthFirstPaths data type.
java.lang.Iterable<java.lang.Integer>	pathTo(int v) Returns a shortest path between s (or sources) and v, or null if no such path.

Methods inherited from class java.lang.Object

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

Constructor Detail

BreadthFirstPaths

public BreadthFirstPaths(Graph G,
                 int s)

Computes the shortest path between s and every other vertex in graph G.

Parameters:

G - the graph

s - the source vertex

BreadthFirstPaths

public BreadthFirstPaths(Graph G,
                 java.lang.Iterable<java.lang.Integer> sources)

Computes the shortest path between any one of the source vertices in sources and every other vertex in graph G.

Parameters:

G - the graph

sources - the source vertices

Method Detail

hasPathTo

public boolean hasPathTo(int v)

Is there a path between the source s (or sources) and vertex v?

Parameters:

v - the vertex

Returns:

true if there is a path, false otherwise

distTo

public int distTo(int v)

Returns the number of edges in a shortest path between the source s (or sources) and vertex v?

Parameters:

v - the vertex

Returns:

the number of edges in a shortest path

pathTo

public java.lang.Iterable<java.lang.Integer> pathTo(int v)

Returns a shortest path between s (or sources) and v, or null if no such path.

Parameters:

v - the vertex

Returns:

the sequence of vertices on a shortest path, as an Iterable

main

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

Unit tests the BreadthFirstPaths data type.