Our implementation of shortestPathLengths in Code Fragment 14.13 relies on use of ?infinity? as a numeric value, to represent the distance bound for vertices that are not (yet) known to be reachable from the source. Reimplement that method without such a sentinel, so that vertices, other than the source, are not added to the priority queue until it is evident that they are reachable.

Transcribed Image Text:

1 /** Computes shortest-path distances from src vertex to all reachable vertices of g. */ 2 public static Map, Integer> 3 shortestPathLengths(Graph g, Vertex src) { 4 // d.get(v) is upper bound on distance from src to v Map, Integer> d = new ProbeHashMap<>(); // map reachable v to its d value 7 5 Map, Integer> cloud = new ProbeHashMap<>(); 8 // pq will have vertices as elements, with d.get(v) as key AdaptablePriorityQueue> pq; 10 9 pq = new HeapAdaptablePriorityQueue<>(); // maps from vertex to its pq locator 12 11 Map, Entry>> pqTokens; pqTokens = new ProbeHashMap<>(); 13 14 15 // for each vertex v of the graph, add an entry to the priority queue, with // the source having distance 0 and all others having infinite distance for (Vertex v : g.vertices( )) { if (v == src) d.put(v,0); else 16 17 18 19 20 21 d.put(v, Integer.MAX_VALUE); pq Tokens.put(v, pq.insert(d.get(v), v)); } // now begin adding reachable vertices to the cloud while (!pq.isEmpty()) { Entry> entry = pq.removeMin( ); int key = entry.getKey(); Vertex u = entry.getValue(); cloud.put(u, key); pq Tokens.remove(u); for (Edge e : g.outgoingEdges(u)) { Vertex v = g.opposite(u,e); if (cloud.get(v) = // perform relaxation step on edge (u,v) int wgt = e.getElement( ); if (d. d.put(v, d.get(u) + wgt); pq.replaceKey(pqTokens.get(v), d.get(v)); // update the pq entry } } } } return cloud; 22 // save entry for future updates 23 24 25 26 27 28 // this is actual distance to u // u is no longer in pq 29 30 31 32 33 null) { 34 35 // better path to v? // update the distance 36 (u) + wgt < d.get(v)) - 37 38 39 40 41 42 43 // this only includes reachable vertices 44 }