public class BellmanFordSP extends Object
BellmanFordSP
class represents a data type for solving the
single-source shortest paths problem in edge-weighted 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 queue-based implementation of the Bellman-Ford-Moore 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 edge-weighted digraph).
This correctly computes shortest paths if all arithmetic performed is without floating-point 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.
Constructor and Description |
---|
BellmanFordSP(EdgeWeightedDigraph G,
int s)
Computes a shortest paths tree from
s to every other vertex in
the edge-weighted digraph G . |
Modifier and Type | Method and Description |
---|---|
double |
distTo(int v)
Returns the length of a shortest path from the source vertex
s to vertex v . |
boolean |
hasNegativeCycle()
Is there a negative cycle reachable from the source vertex
s ? |
boolean |
hasPathTo(int v)
Is there a path from the source
s to vertex v ? |
static void |
main(String[] args)
Unit tests the
BellmanFordSP data type. |
Iterable<DirectedEdge> |
negativeCycle()
Returns a negative cycle reachable from the source vertex
s , or null
if there is no such cycle. |
Iterable<DirectedEdge> |
pathTo(int v)
Returns a shortest path from the source
s to vertex v . |
public BellmanFordSP(EdgeWeightedDigraph G, int s)
s
to every other vertex in
the edge-weighted digraph G
.G
- the acyclic digraphs
- the source vertexIllegalArgumentException
- unless 0 <= s < V
public boolean hasNegativeCycle()
s
?true
if there is a negative cycle reachable from the
source vertex s
, and false
otherwisepublic Iterable<DirectedEdge> negativeCycle()
s
, or null
if there is no such cycle.s
as an iterable of edges, and null
if there is no such cyclepublic double distTo(int v)
s
to vertex v
.v
- the destination vertexs
to vertex v
;
Double.POSITIVE_INFINITY
if no such pathUnsupportedOperationException
- if there is a negative cost cycle reachable
from the source vertex s
IllegalArgumentException
- unless 0 <= v < V
public boolean hasPathTo(int v)
s
to vertex v
?v
- the destination vertextrue
if there is a path from the source vertex
s
to vertex v
, and false
otherwiseIllegalArgumentException
- unless 0 <= v < V
public Iterable<DirectedEdge> pathTo(int v)
s
to vertex v
.v
- the destination vertexs
to vertex v
as an iterable of edges, and null
if no such pathUnsupportedOperationException
- if there is a negative cost cycle reachable
from the source vertex s
IllegalArgumentException
- unless 0 <= v < V
public static void main(String[] args)
BellmanFordSP
data type.args
- the command-line arguments