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.