Class BellmanFordSP
 Object

 edu.princeton.cs.algs4.BellmanFordSP

public class BellmanFordSP extends Object
TheBellmanFordSP
class represents a data type for solving the singlesource shortest paths problem in edgeweighted digraphs with no negative cycles. The edge weights can be positive, negative, or zero. This class finds either a shortest path from the source vertex s to every other vertex or a negative cycle reachable from the source vertex.This implementation uses a queuebased implementation of the BellmanFordMoore algorithm. The constructor takes Θ(E V) time in the worst case, where V is the number of vertices and E is the number of edges. In practice, it performs much better. Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the edgeweighted digraph).
This correctly computes shortest paths if all arithmetic performed is without floatingpoint rounding error or arithmetic overflow. This is the case if all edge weights are integers and if none of the intermediate results exceeds 2^{52}. Since all intermediate results are sums of edge weights, they are bounded by V C, where V is the number of vertices and C is the maximum absolute value of any edge weight.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Constructor Summary
Constructors Constructor Description BellmanFordSP(EdgeWeightedDigraph G, int s)
Computes a shortest paths tree froms
to every other vertex in the edgeweighted digraphG
.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description double
distTo(int v)
Returns the length of a shortest path from the source vertexs
to vertexv
.boolean
hasNegativeCycle()
Is there a negative cycle reachable from the source vertexs
?boolean
hasPathTo(int v)
Is there a path from the sources
to vertexv
?static void
main(String[] args)
Unit tests theBellmanFordSP
data type.Iterable<DirectedEdge>
negativeCycle()
Returns a negative cycle reachable from the source vertexs
, ornull
if there is no such cycle.Iterable<DirectedEdge>
pathTo(int v)
Returns a shortest path from the sources
to vertexv
.



Constructor Detail

BellmanFordSP
public BellmanFordSP(EdgeWeightedDigraph G, int s)
Computes a shortest paths tree froms
to every other vertex in the edgeweighted digraphG
. Parameters:
G
 the acyclic digraphs
 the source vertex Throws:
IllegalArgumentException
 unless0 <= s < V


Method Detail

hasNegativeCycle
public boolean hasNegativeCycle()
Is there a negative cycle reachable from the source vertexs
? Returns:
true
if there is a negative cycle reachable from the source vertexs
, andfalse
otherwise

negativeCycle
public Iterable<DirectedEdge> negativeCycle()
Returns a negative cycle reachable from the source vertexs
, ornull
if there is no such cycle. Returns:
 a negative cycle reachable from the source vertex
s
as an iterable of edges, andnull
if there is no such cycle

distTo
public double distTo(int v)
Returns the length of a shortest path from the source vertexs
to vertexv
. Parameters:
v
 the destination vertex Returns:
 the length of a shortest path from the source vertex
s
to vertexv
;Double.POSITIVE_INFINITY
if no such path  Throws:
UnsupportedOperationException
 if there is a negative cost cycle reachable from the source vertexs
IllegalArgumentException
 unless0 <= v < V

hasPathTo
public boolean hasPathTo(int v)
Is there a path from the sources
to vertexv
? Parameters:
v
 the destination vertex Returns:
true
if there is a path from the source vertexs
to vertexv
, andfalse
otherwise Throws:
IllegalArgumentException
 unless0 <= v < V

pathTo
public Iterable<DirectedEdge> pathTo(int v)
Returns a shortest path from the sources
to vertexv
. Parameters:
v
 the destination vertex Returns:
 a shortest path from the source
s
to vertexv
as an iterable of edges, andnull
if no such path  Throws:
UnsupportedOperationException
 if there is a negative cost cycle reachable from the source vertexs
IllegalArgumentException
 unless0 <= v < V

main
public static void main(String[] args)
Unit tests theBellmanFordSP
data type. Parameters:
args
 the commandline arguments

