edu.princeton.cs.algs4

## Class BellmanFordSP

• Object
• edu.princeton.cs.algs4.BellmanFordSP

• ```public class BellmanFordSP
extends Object```
The `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 252. 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 and Description
```BellmanFordSP(EdgeWeightedDigraph G, int s)```
Computes a shortest paths tree from `s` to every other vertex in the edge-weighted digraph `G`.
• ### Method Summary

All Methods
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`.
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### BellmanFordSP

```public BellmanFordSP(EdgeWeightedDigraph G,
int s)```
Computes a shortest paths tree from `s` to every other vertex in the edge-weighted digraph `G`.
Parameters:
`G` - the acyclic digraph
`s` - the source vertex
Throws:
`IllegalArgumentException` - unless `0 <= s < V`
• ### Method Detail

• #### hasNegativeCycle

`public boolean hasNegativeCycle()`
Is there a negative cycle reachable from the source vertex `s`?
Returns:
`true` if there is a negative cycle reachable from the source vertex `s`, and `false` otherwise
• #### negativeCycle

`public Iterable<DirectedEdge> negativeCycle()`
Returns a negative cycle reachable from the source vertex `s`, or `null` if there is no such cycle.
Returns:
a negative cycle reachable from the soruce vertex `s` as an iterable of edges, and `null` if there is no such cycle
• #### distTo

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

`public boolean hasPathTo(int v)`
Is there a path from the source `s` to vertex `v`?
Parameters:
`v` - the destination vertex
Returns:
`true` if there is a path from the source vertex `s` to vertex `v`, and `false` otherwise
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• #### pathTo

`public Iterable<DirectedEdge> pathTo(int v)`
Returns a shortest path from the source `s` to vertex `v`.
Parameters:
`v` - the destination vertex
Returns:
a shortest path from the source `s` to vertex `v` as an iterable of edges, and `null` if no such path
Throws:
`UnsupportedOperationException` - if there is a negative cost cycle reachable from the source vertex `s`
`IllegalArgumentException` - unless `0 <= v < V`
• #### main

`public static void main(String[] args)`
Unit tests the `BellmanFordSP` data type.
Parameters:
`args` - the command-line arguments