public class BellmanFordSP extends Object
This implementation uses the Bellman-Ford-Moore algorithm. The constructor takes time proportional to V (V + E) in the worst case, where V is the number of vertices and E is the number of edges. Afterwards, the distTo(), hasPathTo(), and hasNegativeCycle() methods take constant time; the pathTo() and negativeCycle() method takes time proportional to the number of edges returned.
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)
G - the acyclic digraphs - the source vertexIllegalArgumentException - unless 0 ≤ s ≤ V - 1public boolean hasNegativeCycle()
public Iterable<DirectedEdge> negativeCycle()
public double distTo(int v)
v - the destination vertexUnsupportedOperationException - if there is a negative cost cycle reachable
from the source vertex spublic boolean hasPathTo(int v)
v - the destination vertexpublic Iterable<DirectedEdge> pathTo(int v)
v - the destination vertexUnsupportedOperationException - if there is a negative cost cycle reachable
from the source vertex spublic static void main(String[] args)
Copyright © 2014. All Rights Reserved.