check attached files
/****************************************************************************** * Compilation: javac DijkstraSP.java * Execution: java DijkstraSP input.txt s * Dependencies: EdgeWeightedDigraph.java IndexMinPQ.java Stack.java DirectedEdge.java * Data files: https://algs4.cs.princeton.edu/44sp/tinyEWD.txt * https://algs4.cs.princeton.edu/44sp/mediumEWD.txt * https://algs4.cs.princeton.edu/44sp/largeEWD.txt * * Dijkstra's algorithm. Computes the shortest path tree. * Assumes all weights are non-negative. * * % java DijkstraSP tinyEWD.txt 0 * 0 to 0 (0.00) * 0 to 1 (1.05) 0->4 0.38 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.38) 0->4 0.38 * 0 to 5 (0.73) 0->4 0.38 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 DijkstraSP mediumEWD.txt 0 * 0 to 0 (0.00) * 0 to 1 (0.71) 0->44 0.06 44->93 0.07 ... 107->1 0.07 * 0 to 2 (0.65) 0->44 0.06 44->231 0.10 ... 42->2 0.11 * 0 to 3 (0.46) 0->97 0.08 97->248 0.09 ... 45->3 0.12 * 0 to 4 (0.42) 0->44 0.06 44->93 0.07 ... 77->4 0.11 * ... * ******************************************************************************/ package edu.princeton.cs.algs4; /** * The {@code DijkstraSP} class represents a data type for solving the * single-source shortest paths problem in edge-weighted digraphs * where the edge weights are non-negative. *
* This implementation uses
Dijkstra's algorithm
with a *
binary heap. The constructor takes * Θ(E
log
V) time in the worst case, * where
V
is the number of vertices and
E
is * the number of edges. 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 * weight of any edge. *
* For additional documentation, * see
Section 4.4
of *
Algorithms, 4th Edition
by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class DijkstraSP { private double[] distTo; // distTo[v] = distance of shortest s->v path private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path private IndexMinPQ pq; // priority queue of vertices /** * Computes a shortest-paths tree from the source vertex {@code s} to every other * vertex in the edge-weighted digraph {@code G}. * * @param G the edge-weighted digraph * @param s the source vertex * @throws IllegalArgumentException if an edge weight is negative * @throws IllegalArgumentException unless {@code 0 <= s="">< v}="" */="" public="" dijkstrasp(edgeweighteddigraph="" g,="" int="" s)="" {="" for="" (directededge="" e="" :="" g.edges())="" {="" if="" (e.weight()="">< 0)="" throw="" new="" illegalargumentexception("edge="" "="" +="" e="" +="" "="" has="" negative="" weight");="" }="" distto="new" double[g.v()];="" edgeto="new" directededge[g.v()];="" validatevertex(s);="" for="" (int="" v="0;" v="">< g.v();="" v++)="" distto[v]="Double.POSITIVE_INFINITY;" distto[s]="0.0;" relax="" vertices="" in="" order="" of="" distance="" from="" s="" pq="new">(G.V()); pq.insert(s, distTo[s]); while (!pq.isEmpty()) { int v = pq.delMin(); for (DirectedEdge e : G.adj(v)) relax(e); } // check optimality conditions assert check(G, s); } // relax edge e and update pq if changed private void relax(DirectedEdge e) { int v = e.from(), w = e.to(); if (distTo[w] > distTo[v] + e.weight()) { distTo[w] = distTo[v] + e.weight(); edgeTo[w] = e; if (pq.contains(w)) pq.decreaseKey(w, distTo[w]); else pq.insert(w, distTo[w]); } } /** * Returns the length of a shortest path from the source vertex {@code s} to vertex {@code v}. * @param v the destination vertex * @return the length of a shortest path from the source vertex {@code s} to vertex {@code v}; * {@code Double.POSITIVE_INFINITY} if no such path * @throws IllegalArgumentException unless {@code 0 <= v="">< v}="" */="" public="" double="" distto(int="" v)="" {="" validatevertex(v);="" return="" distto[v];="" }="" **="" *="" returns="" true="" if="" there="" is="" a="" path="" from="" the="" source="" vertex="" {@code="" s}="" to="" vertex="" {@code="" v}.="" *="" *="" @param="" v="" the="" destination="" vertex="" *="" @return="" {@code="" true}="" if="" there="" is="" a="" path="" from="" the="" source="" vertex="" *="" {@code="" s}="" to="" vertex="" {@code="" v};="" {@code="" false}="" otherwise="" *="" @throws="" illegalargumentexception="" unless="" {@code="" 0=""><= v="">< v}="" */="" public="" boolean="" haspathto(int="" v)="" {="" validatevertex(v);="" return="" distto[v]="">< double.positive_infinity;="" }="" **="" *="" returns="" a="" shortest="" path="" from="" the="" source="" vertex="" {@code="" s}="" to="" vertex="" {@code="" v}.="" *="" *="" @param="" v="" the="" destination="" vertex="" *="" @return="" a="" shortest="" path="" from="" the="" source="" vertex="" {@code="" s}="" to="" vertex="" {@code="" v}="" *="" as="" an="" iterable="" of="" edges,="" and="" {@code="" null}="" if="" no="" such="" path="" *="" @throws="" illegalargumentexception="" unless="" {@code="" 0=""><= v="">< v}="" */="" public=""> pathTo(int v) { validateVertex(v); if (!hasPathTo(v)) return null; Stack path = new Stack(); for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) { path.push(e); } return path; } // check optimality conditions: // (i) for all edges e: distTo[e.to()] <= distto[e.from()]="" +="" e.weight()="" (ii)="" for="" all="" edge="" e="" on="" the="" spt:="" distto[e.to()]="=" distto[e.from()]="" +="" e.weight()="" private="" boolean="" check(edgeweighteddigraph="" g,="" int="" s)="" {="" check="" that="" edge="" weights="" are="" non-negative="" for="" (directededge="" e="" :="" g.edges())="" {="" if="" (e.weight()="">< 0)="" {="" system.err.println("negative="">