public class BellmanFordSP
extends java.lang.Object
Compilation: javac BellmanFordSP.java
Execution: java BellmanFordSP filename.txt s
Dependencies: EdgeWeightedDigraph.java DirectedEdge.java Queue.java
EdgeWeightedDirectedCycle.java
Data files: http://algs4.cs.princeton.edu/44sp/tinyEWDn.txt
http://algs4.cs.princeton.edu/44sp/mediumEWDnc.txt
Bellman-Ford shortest path algorithm. Computes the shortest path tree in
edge-weighted digraph G from vertex s, or finds a negative cost cycle
reachable from s.
% java BellmanFordSP tinyEWDn.txt 0
0 to 0 ( 0.00)
0 to 1 ( 0.93) 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52 6->4 -1.25 4->5 0.35 5->1 0.32
0 to 2 ( 0.26) 0->2 0.26
0 to 3 ( 0.99) 0->2 0.26 2->7 0.34 7->3 0.39
0 to 4 ( 0.26) 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52 6->4 -1.25
0 to 5 ( 0.61) 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52 6->4 -1.25 4->5 0.35
0 to 6 ( 1.51) 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52
0 to 7 ( 0.60) 0->2 0.26 2->7 0.34
% java BellmanFordSP tinyEWDnc.txt 0
4->5 0.35
5->4 -0.66