001package algs44; 002import stdlib.*; 003import algs13.Stack; 004import algs24.IndexMinPQ; 005/* *********************************************************************** 006 * Compilation: javac DijkstraSP.java 007 * Execution: java DijkstraSP input.txt s 008 * Dependencies: EdgeWeightedDigraph.java IndexMinPQ.java Stack.java DirectedEdge.java 009 * Data files: http://algs4.cs.princeton.edu/44sp/tinyEWD.txt 010 * http://algs4.cs.princeton.edu/44sp/mediumEWD.txt 011 * http://algs4.cs.princeton.edu/44sp/largeEWD.txt 012 * 013 * Dijkstra's algorithm. Computes the shortest path tree. 014 * Assumes all weights are nonnegative. 015 * 016 * % java DijkstraSP tinyEWD.txt 0 017 * 0 to 0 (0.00) 018 * 0 to 1 (1.05) 0->4 0.38 4->5 0.35 5->1 0.32 019 * 0 to 2 (0.26) 0->2 0.26 020 * 0 to 3 (0.99) 0->2 0.26 2->7 0.34 7->3 0.39 021 * 0 to 4 (0.38) 0->4 0.38 022 * 0 to 5 (0.73) 0->4 0.38 4->5 0.35 023 * 0 to 6 (1.51) 0->2 0.26 2->7 0.34 7->3 0.39 3->6 0.52 024 * 0 to 7 (0.60) 0->2 0.26 2->7 0.34 025 * 026 * % java DijkstraSP mediumEWD.txt 0 027 * 0 to 0 (0.00) 028 * 0 to 1 (0.71) 0->44 0.06 44->93 0.07 ... 107->1 0.07 029 * 0 to 2 (0.65) 0->44 0.06 44->231 0.10 ... 42->2 0.11 030 * 0 to 3 (0.46) 0->97 0.08 97->248 0.09 ... 45->3 0.12 031 * 0 to 4 (0.42) 0->44 0.06 44->93 0.07 ... 77->4 0.11 032 * ... 033 * 034 *************************************************************************/ 035 036public class DijkstraSP { 037 private final double[] distTo; // distTo[v] = distance of shortest s->v path 038 private final DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path 039 private final IndexMinPQ<Double> pq; // priority queue of vertices 040 041 public DijkstraSP(EdgeWeightedDigraph G, int s) { 042 for (DirectedEdge e : G.edges()) { 043 if (e.weight() < 0) 044 throw new IllegalArgumentException("edge " + e + " has negative weight"); 045 } 046 047 distTo = new double[G.V()]; 048 edgeTo = new DirectedEdge[G.V()]; 049 for (int v = 0; v < G.V(); v++) 050 distTo[v] = Double.POSITIVE_INFINITY; 051 distTo[s] = 0.0; 052 053 // relax vertices in order of distance from s 054 pq = new IndexMinPQ<>(G.V()); 055 pq.insert(s, distTo[s]); 056 while (!pq.isEmpty()) { 057 int v = pq.delMin(); 058 for (DirectedEdge e : G.adj(v)) 059 relax(e); 060 } 061 062 // check optimality conditions 063 assert check(G, s); 064 } 065 066 // relax edge e and update pq if changed 067 private void relax(DirectedEdge e) { 068 int v = e.from(), w = e.to(); 069 if (distTo[w] > distTo[v] + e.weight()) { 070 distTo[w] = distTo[v] + e.weight(); 071 edgeTo[w] = e; 072 if (pq.contains(w)) pq.decreaseKey(w, distTo[w]); 073 else pq.insert(w, distTo[w]); 074 } 075 } 076 077 // length of shortest path from s to v 078 public double distTo(int v) { 079 return distTo[v]; 080 } 081 082 // is there a path from s to v? 083 public boolean hasPathTo(int v) { 084 return distTo[v] < Double.POSITIVE_INFINITY; 085 } 086 087 // shortest path from s to v as an Iterable, null if no such path 088 public Iterable<DirectedEdge> pathTo(int v) { 089 if (!hasPathTo(v)) return null; 090 Stack<DirectedEdge> path = new Stack<>(); 091 for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) { 092 path.push(e); 093 } 094 return path; 095 } 096 097 098 // check optimality conditions: 099 // (i) for all edges e: distTo[e.to()] <= distTo[e.from()] + e.weight() 100 // (ii) for all edge e on the SPT: distTo[e.to()] == distTo[e.from()] + e.weight() 101 private boolean check(EdgeWeightedDigraph G, int s) { 102 103 // check that edge weights are nonnegative 104 for (DirectedEdge e : G.edges()) { 105 if (e.weight() < 0) { 106 System.err.println("negative edge weight detected"); 107 return false; 108 } 109 } 110 111 // check that distTo[v] and edgeTo[v] are consistent 112 if (distTo[s] != 0.0 || edgeTo[s] != null) { 113 System.err.println("distTo[s] and edgeTo[s] inconsistent"); 114 return false; 115 } 116 for (int v = 0; v < G.V(); v++) { 117 if (v == s) continue; 118 if (edgeTo[v] == null && distTo[v] != Double.POSITIVE_INFINITY) { 119 System.err.println("distTo[] and edgeTo[] inconsistent"); 120 return false; 121 } 122 } 123 124 // check that all edges e = v->w satisfy distTo[w] <= distTo[v] + e.weight() 125 for (int v = 0; v < G.V(); v++) { 126 for (DirectedEdge e : G.adj(v)) { 127 int w = e.to(); 128 if (distTo[v] + e.weight() < distTo[w]) { 129 System.err.println("edge " + e + " not relaxed"); 130 return false; 131 } 132 } 133 } 134 135 // check that all edges e = v->w on SPT satisfy distTo[w] == distTo[v] + e.weight() 136 for (int w = 0; w < G.V(); w++) { 137 if (edgeTo[w] == null) continue; 138 DirectedEdge e = edgeTo[w]; 139 int v = e.from(); 140 if (w != e.to()) return false; 141 if (distTo[v] + e.weight() != distTo[w]) { 142 System.err.println("edge " + e + " on shortest path not tight"); 143 return false; 144 } 145 } 146 return true; 147 } 148 149 150 public static void main(String[] args) { 151 In in = new In(args[0]); 152 EdgeWeightedDigraph G = new EdgeWeightedDigraph(in); 153 int s = Integer.parseInt(args[1]); 154 155 // compute shortest paths 156 DijkstraSP sp = new DijkstraSP(G, s); 157 158 159 // print shortest path 160 for (int t = 0; t < G.V(); t++) { 161 if (sp.hasPathTo(t)) { 162 StdOut.format("%d to %d (%.2f) ", s, t, sp.distTo(t)); 163 if (sp.hasPathTo(t)) { 164 for (DirectedEdge e : sp.pathTo(t)) { 165 StdOut.print(e + " "); 166 } 167 } 168 StdOut.println(); 169 } 170 else { 171 StdOut.format("%d to %d no path\n", s, t); 172 } 173 } 174 } 175 176}