001package algs44; 002import stdlib.*; 003import algs13.Queue; 004import algs13.Stack; 005/* *********************************************************************** 006 * Compilation: javac BellmanFordSP.java 007 * Execution: java BellmanFordSP filename.txt s 008 * Dependencies: EdgeWeightedDigraph.java DirectedEdge.java Queue.java 009 * EdgeWeightedDirectedCycle.java 010 * Data files: http://algs4.cs.princeton.edu/44sp/tinyEWDn.txt 011 * http://algs4.cs.princeton.edu/44sp/mediumEWDnc.txt 012 * 013 * Bellman-Ford shortest path algorithm. Computes the shortest path tree in 014 * edge-weighted digraph G from vertex s, or finds a negative cost cycle 015 * reachable from s. 016 * 017 * % java BellmanFordSP tinyEWDn.txt 0 018 * 0 to 0 ( 0.00) 019 * 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 020 * 0 to 2 ( 0.26) 0->2 0.26 021 * 0 to 3 ( 0.99) 0->2 0.26 2->7 0.34 7->3 0.39 022 * 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 023 * 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 024 * 0 to 6 ( 1.51) 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52 025 * 0 to 7 ( 0.60) 0->2 0.26 2->7 0.34 026 * 027 * % java BellmanFordSP tinyEWDnc.txt 0 028 * 4->5 0.35 029 * 5->4 -0.66 030 * 031 *************************************************************************/ 032 033public class BellmanFordSP { 034 private final double[] distTo; // distTo[v] = distance of shortest s->v path 035 private final DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path 036 private final boolean[] onQueue; // onQueue[v] = is v currently on the queue? 037 private final Queue<Integer> queue; // queue of vertices to relax 038 private int cost; // number of calls to relax() 039 private Iterable<DirectedEdge> cycle; // negative cycle (or null if no such cycle) 040 041 public BellmanFordSP(EdgeWeightedDigraph G, int s) { 042 distTo = new double[G.V()]; 043 edgeTo = new DirectedEdge[G.V()]; 044 onQueue = new boolean[G.V()]; 045 for (int v = 0; v < G.V(); v++) 046 distTo[v] = Double.POSITIVE_INFINITY; 047 distTo[s] = 0.0; 048 049 // Bellman-Ford algorithm 050 queue = new Queue<>(); 051 queue.enqueue(s); 052 onQueue[s] = true; 053 while (!queue.isEmpty() && !hasNegativeCycle()) { 054 int v = queue.dequeue(); 055 onQueue[v] = false; 056 relax(G, v); 057 } 058 059 assert check(G, s); 060 } 061 062 // relax vertex v and put other endpoints on queue if changed 063 private void relax(EdgeWeightedDigraph G, int v) { 064 for (DirectedEdge e : G.adj(v)) { 065 int w = e.to(); 066 if (distTo[w] > distTo[v] + e.weight()) { 067 distTo[w] = distTo[v] + e.weight(); 068 edgeTo[w] = e; 069 if (!onQueue[w]) { 070 queue.enqueue(w); 071 onQueue[w] = true; 072 } 073 } 074 if (cost++ % G.V() == 0) 075 findNegativeCycle(); 076 } 077 } 078 079 080 // is there a negative cycle reachable from s? 081 public boolean hasNegativeCycle() { 082 return cycle != null; 083 } 084 085 // return a negative cycle; null if no such cycle 086 public Iterable<DirectedEdge> negativeCycle() { 087 return cycle; 088 } 089 090 // by finding a cycle in predecessor graph 091 private void findNegativeCycle() { 092 int V = edgeTo.length; 093 EdgeWeightedDigraph spt = new EdgeWeightedDigraph(V); 094 for (int v = 0; v < V; v++) 095 if (edgeTo[v] != null) 096 spt.addEdge(edgeTo[v]); 097 098 EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(spt); 099 cycle = finder.cycle(); 100 } 101 102 // is there a path from s to v? 103 public boolean hasPathTo(int v) { 104 return distTo[v] < Double.POSITIVE_INFINITY; 105 } 106 107 108 // return length of shortest path from s to v 109 public double distTo(int v) { 110 return distTo[v]; 111 } 112 113 // return view of shortest path from s to v, null if no such path 114 public Iterable<DirectedEdge> pathTo(int v) { 115 if (!hasPathTo(v)) return null; 116 Stack<DirectedEdge> path = new Stack<>(); 117 for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) { 118 path.push(e); 119 } 120 return path; 121 } 122 123 // check optimality conditions: either 124 // (i) there exists a negative cycle reacheable from s 125 // or 126 // (ii) for all edges e = v->w: distTo[w] <= distTo[v] + e.weight() 127 // (ii') for all edges e = v->w on the SPT: distTo[w] == distTo[v] + e.weight() 128 private boolean check(EdgeWeightedDigraph G, int s) { 129 130 // has a negative cycle 131 if (hasNegativeCycle()) { 132 double weight = 0.0; 133 for (DirectedEdge e : negativeCycle()) { 134 weight += e.weight(); 135 } 136 if (weight >= 0.0) { 137 System.err.println("error: weight of negative cycle = " + weight); 138 return false; 139 } 140 } 141 142 // no negative cycle reachable from source 143 else { 144 145 // check that distTo[v] and edgeTo[v] are consistent 146 if (distTo[s] != 0.0 || edgeTo[s] != null) { 147 System.err.println("distanceTo[s] and edgeTo[s] inconsistent"); 148 return false; 149 } 150 for (int v = 0; v < G.V(); v++) { 151 if (v == s) continue; 152 if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) { 153 System.err.println("distTo[] and edgeTo[] inconsistent"); 154 return false; 155 } 156 } 157 158 // check that all edges e = v->w satisfy distTo[w] <= distTo[v] + e.weight() 159 for (int v = 0; v < G.V(); v++) { 160 for (DirectedEdge e : G.adj(v)) { 161 int w = e.to(); 162 if (distTo[v] + e.weight() < distTo[w]) { 163 System.err.println("edge " + e + " not relaxed"); 164 return false; 165 } 166 } 167 } 168 169 // check that all edges e = v->w on SPT satisfy distTo[w] == distTo[v] + e.weight() 170 for (int w = 0; w < G.V(); w++) { 171 if (edgeTo[w] == null) continue; 172 DirectedEdge e = edgeTo[w]; 173 int v = e.from(); 174 if (w != e.to()) return false; 175 if (distTo[v] + e.weight() != distTo[w]) { 176 System.err.println("edge " + e + " on shortest path not tight"); 177 return false; 178 } 179 } 180 } 181 182 StdOut.println("Satisfies optimality conditions"); 183 StdOut.println(); 184 return true; 185 } 186 187 188 189 public static void main(String[] args) { 190 In in = new In(args[0]); 191 int s = Integer.parseInt(args[1]); 192 EdgeWeightedDigraph G = new EdgeWeightedDigraph(in); 193 194 BellmanFordSP sp = new BellmanFordSP(G, s); 195 196 // print negative cycle 197 if (sp.hasNegativeCycle()) { 198 for (DirectedEdge e : sp.negativeCycle()) 199 StdOut.println(e); 200 } 201 202 // print shortest paths 203 else { 204 for (int v = 0; v < G.V(); v++) { 205 if (sp.hasPathTo(v)) { 206 StdOut.format("%d to %d (%5.2f) ", s, v, sp.distTo(v)); 207 for (DirectedEdge e : sp.pathTo(v)) { 208 StdOut.print(e + " "); 209 } 210 StdOut.println(); 211 } 212 else { 213 StdOut.format("%d to %d no path\n", s, v); 214 } 215 } 216 } 217 218 } 219 220}