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 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.