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)
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)...
-
In 2020, Janet and Ray are married filing jointly. They have five dependent children under 18 years of age. Janet and Rays taxable income is $2,400,000 and they itemize their deductions as follows:...
-
What performance measure would you consider most important for McDonald's? For Chevrolet?
-
The trial balance of the Garland Company shown below does not balance. Your review of the ledger reveals that each account has a normal balance. You also discover the following errors. 1. The totals...
-
Show that the function is a solution to y(x) = = Ce + Czex d y dy 2y = 0 dx dx for any choice of the constants C1 and C2. Then, determine C1 and C2 so that the initial conditions y(0) = 2 and dxx (0)...
-
Following are the income statement and balance sheet for Medtronic PLC. Consolidated Statement of Income, 12 Months Ended ($ millions) April 26, 2019 Net Sales $30,557 Costs and expenses Cost of...
-
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...
-
In Exercise 6.178 on page 403 we perform a test for the difference in the proportion of penguins who survive over a 10-year period, between penguins tagged with metal tags and those tagged with...
-
What are the implications of continuous and discontinuous change for innovation?
-
Identify the basic characteristics associated with clan, hierarchy, market and adhocracy culture types.
-
Under what situations should you look to source knowledge externally and under what circumstances should it be created internally?
-
Discuss the different roles a subsidiary can play in the roll-out of an innovation.
-
Using an illustrative example, describe the four possible customisation strategies that a firm might adopt.
-
Why is it important not to view the concept of whistle-blowing as tattle-telling or ratting on another employee?
-
Solve the relation Exz:Solve therelation ne %3D
-
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...
-
Evaluating a sinusoidal function that models a real-world situation A mass on a spring is moving with simple harmonic motion. After a time t, the height h of the mass above its rest position is given...
-
Find the following using the table below. 8 1 2243 34 234 -4 3 4 -1 -2 3 -5 -4 -1 1 24 f(x) f'(x) g(x) g'(x) If h(x) = f(x) g(x), then h'(1) = f(x) If k(x) = then k'(1) = g(x) If p(x) = f(g(x)), then...
-
Use interval notation to write the interval(s) over which fis (a) increasing, (b) decreasing, and (c) constant. If there is more than one interval, separate them with commas. 3. 2+ -3 -2 1 2 3 -2
Study smarter with the SolutionInn App