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: 57% (7 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...
-
The following information is available for ADT Company, which produces special - order security products and uses a job order costing system. Overhead is applied using a predetermined overhead rate...
-
Indicate whether each of the following costs related to inventory, a through I, would be considered (1) a purchasing cost, (2) an ordering cost, (3) a carrying cost, or (4) a cost of not carrying...
-
In 2015, a city opens a municipal landll, which it will account for in an enterprise fund. It estimates capacity to be 6 million cubic feet and usable life to be 20 years. To close the landll, the...
-
A study of the amount of time it takes a mechanic to rebuild the transmission for a 1992 Chevrolet Cavalier shows that the mean is 8.4 hours and the standard deviation is 1.8 hours. If 40 mechanics...
-
Superior Hardwood Company distributes hardwood products to small furniture manufacturers. The adjusted trial balance data given below is from the firms worksheet for the year ended December 31, 2019....
-
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)...
-
Construct an E-R diagram for a hospital with a set of patients and a set of medical doctors. Associate with each patient a log of the various tests and examinations conducted.
-
what ways do central banks utilize forward guidance strategies to shape market expectations and influence long-term interest rates, and how effective are these measures in achieving macroeconomic...
-
Twane Ltd. supplied the following information: Direct material: R220 000 Direct Labour: R120 000 Overheads: R120 000 Units manufactured: 5 000 units Required: Determine the total manufacturing cost...
-
The general ledger of Jackrabbit Rentals at January 1, 2024, includes the following account balances: Accounts Debits Credits Cash $43,500 Accounts Receivable 27,700 Land 112,800 Accounts Payable...
-
Required information [The following information applies to the questions displayed below.] Arndt, Incorporated reported the following for 2024 and 2025 ($ in millions): Revenues Expenses 2024 $ 946...
-
A buyer with a $750,000 loan has a monthly principal and interest payment of $4,376.80. If $3,593.75 is interest, what is the new principal balance after the first payment is applied?
-
Here is the textbook by Daft, Richard, "Organization Theory and Design" 12th Cengage Learning, 2016. Read and review and answer the questions: 3. In a rapidly changing organization, are decisions...
-
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?
-
Sidman Products's common stock currently sells for $57 a share. The firm is expected to earn $6.84 per share this year and to pay a year-end dividend of $3.10, and it finances only with common...
-
Problem 1 0 - 1 Relevant Cash Flows [ LO 1 ] Parker & Stone, Incorporated, is looking at setting up a new manufacturing plant in South Park to produce garden tools. The company bought some land six...
-
Using the Hi-Tech data shown in Tables 4.5 and 4.6 below as well as information from the textbook, recalculate the NPV of Hi-Tech; but assume that the company is currently not at its target capital...
Study smarter with the SolutionInn App