Consider the problem of finding the least expensive routes to all cities in a network from a
Question:
Consider the problem of finding the least expensive routes to all cities in a network from a given starting point. For example, in the network shown on the mapbelow, the least expensive route from Pendleton to Peoria has cost 8 (going through Pierre and Pueblo).
When the algorithm has finished, shortestKnownDistance contains the shortest distance from the starting point to all reachable targets.
Transcribed Image Text:
The following helper class expresses the distance to another city: public class Distance To implements Comparable { private String target; private int distance; public DistanceTo (String city, int dist) { target= city; distance = dist; } public String getTarget() { return target; } public int getDistance() { return distance; } public int compareTo (Distance To other) { return distance other.distance; } } All direct connections between cities are stored in a Map . The algorithm now proceeds as follows: Let from be the starting point. Add DistanceTo (from, o) to a priority queue. Construct a map shortest known Distance from city names to distances. While the priority queue is not empty Get its smallest element. If its target is not a key in shortest knownDistance Let d be the distance to that target. Put (target, d) into shortestknownDistance. For all cities c that have a direct connection from target Add DistanceTo(c, d + distance from target to c) to the priority queue.
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 100% (QA)
Based on the details and images you have provided the goal is to implement Dijkstras algorithm to find the shortest path from a starting city the first city in the input file to all other cities in th...View the full answer
Answered By
Ayush Mishra
I am a certified online tutor, with more than 3 years of experience in online tutoring. My tutoring subjects include: Physics, Mathematics and Mechanical engineering. I have also been awarded as best tutor for year 2019 in my previous organisation. Being a Mechanical Engineer, I love to tell the application of the concepts of science and mathematics in the real world. This help students to develop interest and makes learning fun and easy. This in turn, automatically improves their grades in the subject. I teach students to get prepared for college entry level exam. I also use to teach undergraduate students and guide them through their career aim.
5.00+
2+ Reviews
10+ Question Solved
Related Book For
Question Posted:
Students also viewed these Java Programming questions
-
Consider the problem of finding the least expensive routes to all cities in a network from a given starting point. For example, in the network shown on the map on page 733, the least expensive route...
-
Let i and j be positive integers. (i) Prove that there exist natural numbers a and b such that ai = bj+gcd(i, j). You may use standard results provided that you state them clearly. [4 marks] (ii) Let...
-
do the following,..... Write program that reads a person's first and last names, separated by a space. Then the program outputs last name, comma, first name. Create program that takes in user input...
-
A new out-of-state client, Robert Ball, has asked you to prepare a Form 709 for a large gift he made in 2013. When you request copies of any prior gift tax returns he may have filed, he responds,...
-
Refrigerant-134a enters an adiabatic compressor at 15 psia and 20°F with a volume flow rate of 10 ft3/s and leaves at a pressure of 100 psia. The power input to the compressor is 45 hp. Find (a)...
-
Panko Inc. began a business on January 1, 2019. It purchased equipment for its factory on this date for $340,000. The equipment is expected to have an estimated useful life of four years with a...
-
Presented below are summary financial data from the Johnson & Johnson 2015 annual report. Using the ratio definitions from Exhibit 4.6, calculate the following ratios: return on equity, return on...
-
EZ Copy had the transactions listed below during the month of June. Show how each transaction would be recorded in the accounting equation. Compute the totals at the end of the month. The headings to...
-
Credit: 10 and PO Strips (Ch. 20) Saved 1 kipped An investor is considering the purchase of either an IO or PO strip from a CMO offering. The portion of the mortgage pool backing this tranche...
-
On January 1, 2011, Price Company purchased an 80% interest in the common stock of Stahl Company for $1,040,000, which was $60,000 greater than the book value of equity acquired. The difference...
-
The linked list class in the Java library supports operations addLast and removeLast. To carry out these operations efficiently, the LinkedList class has an added reference last to the last node in...
-
Extend Exercise Business P15.12 to a program that can handle shares of multiple companies. The user enters commands buy symbol quantity price and sell symbol quantity price. Keep a Map> that manages...
-
Isabella runs a pet salon. She is currently grooming 125 dogs per week. If instead of grooming 125 dogs, she grooms 126 dogs, she will add $68.50 to her costs and $60.00 to her revenues. What will be...
-
Tariffs and quotas both raise the price of foreign goods to domestic consumers. What is the difference between the effects of a tariff and the effects of a quota on the following? a. The domestic...
-
Read the box "The Economic Value of a Year of Education: Homoskedasticity or Heteroskedasticity?" in Section 5.4. Use the regression reported in Equation (5.23) to answer the following. a. A randomly...
-
Suppose the world price of kiwi fruit is \($25\) per case and the U.S. equilibrium price with no international trade is \($40\) per case. If the U.S. government had previously banned the import of...
-
An econometrics class has 80 students, and the mean student weight is \(145 \mathrm{lb}\). A random sample of 4 students is selected from the class, and their average weight is calculated. Will the...
-
Think of an industry in your country (if you currently have a job, use that industry). What kind of nontariff barrier could you design that would keep out foreign competitors to the domestic...
-
What is the reliance placed in system software working? And when operating systems do not work properly, what are the consequences in business terms?
-
The packaging division of a company having considered several alternative package designs for the company's new product has finally brought down their choices to two designs of which only one has to...
-
In a cellular system, with omni-directional antennas, employs a cluster of size 7. The cell at the center of the cluster has much more traffic than the others and need to borrow some channels from...
-
What are the advantages of cell sectoring? How do you compare this with SDMA?
-
In a cellular system, with 7-cell clusters, has the following average number pf calls at a given time: Cell number Average number of calls/unit time...
-
You want to quit your job and go back to school for a law degree 8 years from now, and you plan to save $ 1 , 6 9 1 per year until then. At the beginning of each year, starting today, you will...
-
provide a cost comparison between building a bamboo house and concrete house
-
Turnbull Co . is considering a project that requires an initial investment of $ 2 7 0 , 0 0 0 . The firm will raise the $ 2 7 0 , 0 0 0 in capital by issuing $ 1 0 0 , 0 0 0 of debt at a before - tax...
Study smarter with the SolutionInn App