Our implementation of shortestPathLengths in Code Fragment 14.13 relies on use of ?infinity? as a numeric value,
Question:
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
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 }
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 66% (6 reviews)
Here is the reimplemented shortestPathLengths method without the use of a sentinel ...View the full answer
Answered By
Akshay Shete
I have extensive experience as a tutor, both online and in-person. I have worked with students of all ages and abilities, and am skilled at adapting my teaching style to meet the needs of each individual student. I have a strong background in a variety of subjects, including math, science, and English, and am able to break down complex concepts in a way that is easy for students to understand. In addition to my subject matter expertise, I am also a patient and supportive teacher, and am committed to helping my students succeed. Whether I am working with a struggling student who needs extra help to catch up, or an advanced student looking to get ahead, I am able to provide the guidance and support they need to reach their goals. Overall, my hands-on experience as a tutor has prepared me to be a confident and effective teacher, and I am excited to use my skills to help students succeed.
0.00
0 Reviews
10+ Question Solved
Related Book For
Data Structures and Algorithms in Java
ISBN: 978-1118771334
6th edition
Authors: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
Question Posted:
Students also viewed these Computer science questions
-
Use the following description of the operations of the RC_Charter2 Company to complete this exercise. ¢ The RC_Charter2 Company operates a fleet of aircraft under the Federal Air Regulations...
-
On July 1, 2013, Lula Plume created a new self-storage business, Safe Storage Co. The following transactions occurred during the companys first month. July 1 Plume invested $30,000 cash and buildings...
-
On April 1, 2011, Jiro Nozomi created a new travel agency, Adventure Travel. The following transactions occurred during the companys first month. April 1 Nozomi invested $32,000 cash and computer...
-
Suppose that In Example 18.6 the electrical firm does not have enough prior information regarding the population mean length of life to be able to assume a normal distribution for p. The firm...
-
Capitol Life Insurance Company ("Capitol") was incorporated in the U.S.A. in the state of Colorado at the turn of the century. Its head office had always been in Denver, Colorado. Capitol was a...
-
Business model innovation is an important part of the entrepreneurial process. Not only do entrepreneurs bring new products and services to market, but new business models often revolutionize how...
-
Make decisions in the situations described in the Ethical Behavior Worksheet. You will not have all the background information on each situation; instead, you should make whatever assumptions you...
-
Assume that the auditors encountered the following sepa-rate situations when deciding on the report to issue for the current- year financial statements. 1. The auditors decided that sufficient...
-
An 8,000-seat amphitheater will sell tickets at $70 and $125 for an Aerosmith concert. Assuming the concert sells out, the revenue will be $763,500. How many of each type of ticket need to be sold to...
-
Chicken feed is transported by trucks from three silos to four farms. Some of the silos cannot ship directly to some of the farms. The capacities of the other routes are limited by the number of...
-
Give an example of a weighted directed graph G with negative-weight edges, but no negative-weight cycle, such that Dijkstras algorithm incorrectly computes the shortest-path distances from some start...
-
An old MST method, called Baruvka?s algorithm, works as follows on a graph G having n vertices and m edges with distinct weights: Prove that this algorithm is correct and that it runs in O(mlogn)...
-
$750 is what percent more than $250?
-
Assembly Department Beginning work in process inventory Units started this period Units completed and transferred out Ending work in process inventory Cost of beginning work in process Direct...
-
3 Finished goods inventory, beginning Finished goods inventory, ending Depreciation on factory equipment Direct labor Indirect labor Factory utilities Selling expenses Direct materials used Indirect...
-
Question 2 2 : When creating a flowchart, you do not need to ensure that the steps follow logic. Question 2 2 options: True False
-
To add two fixed point numbers Group of answer choices The same adder circuit that adds two integer numbers can be used. We need an adder circuit fixed to wall. None Impossible to add two fixed point...
-
(CLO 1: Cognitive Level C2 (Understanding)) (PLO 1: Engineering Knowledge) Q2: The image below has 64 grey levels (0-63). Employ a 3x3 Sobel filter in both horizontal and vertical direction to the...
-
Armstrong Incorporated, a Texas corporation, runs bicycle tours in several states. Armstrong also has a Texas retail store and an Internet store that ships to out-of-state customers. The bicycle...
-
Suppose the concentration of glucose inside a cell is 0.1 mm and the cell is suspended in a glucose solution of 0.01 mm. a. What would be the free energy change involved in transporting 10-o mole of...
-
What is the purpose of the SNMP trap message?
-
In Section 5.7 we saw that it was preferable to transport SNMP messages in unreliable UDP data-grams. Why do you think the designers of SNMP chose UDP rather than TCP as the transport protocol of...
-
What are the purposes of the SNMP Get Request and Set Request messages?
-
Link to Digital Profile/Portfolio 2. You are taking a database snapshot of your RDS instance. What would be the impact to the I/O operations while taking snapshots? 3. What is the maximum size of RDS...
-
Define Divide and Conquer Run the simulation of merge sort in: https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/ (not a question) Explain the algorithm of merge sort? Does...
-
Ask a non-IT person (your friend, child) how the Web is different from the Internet. Quote the most interesting part of their answer and then critique it based on what you know. Explain the process...
Study smarter with the SolutionInn App