For example, in this network, the least expensive route from Pendleton to Peoria
ID: 3691608 • Letter: F
Question
For example, in this network, the least expensive route from Pendleton to Peoria has cost 8 (going through Pierre and Pueblo).
The following helper class expresses the distance to another city:
public class DistanceTo implements Comparable<DistanceTo>
{
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(DistanceTo other)
{
return distance - other.distance;
}
}
All direct connections between cities are stored in a Map<String, TreeSet<DistanceTo>>.
The algorithm now proceeds as follows:
Let from be the starting point.
Add DistanceTo(from, 0) to a priority queue.
Construct a map shortestKnownDistance from city names to distances.
While the priority queue is not empty:
Get its smallest element.
If its target is not a key in shortestKnownDistance:
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.
When the algorithm has finished, shortestKnownDistance contains the shortest distance from the starting point to all reachable targets.
Your task is to write a program that implements this algorithm:
Your program should read in lines of the form city1 city2 distance.
HINT: Consider using the Java class java.util.StringTokenizer
The starting point is the first city in the first line.
Print the shortest distances to all other cities.
Sample Run:
Shortest distances from Pierre:
Distance to Pensacola is 4
Distance to Pendleton is 2
Distance to Pierre is 0
Distance to Pueblo is 3
Distance to Peoria is 4
Distance to Phoenix is 9
Distance to Pittsburgh is 2
Explanation / Answer
A location cannot appear more than once in the path, hence A - B - Y - U - P - U - Z is not valid.
Locations are named AAA to ZZZ (presented here as A - Z for simplicity) and the input is random in such a way that there may or may not be a location ABC, all locations may be XXX (unlikely), or there may not be a possible path at all locations are "isolated".
Initially I'd thought that this is a variation of the unweighted shortest path problem, but I find it rather different and I'm not sure how does the algorithm there apply here.
My current solution goes like this:
Pre-process the list such that we have a hashmap which points a location (left), to a list of locations (right)
Create a hashmap to keep track of "visited locations". Create a list to store "found paths".
Store X (starting-location) to the "visited locations" hashmap.
Search for X in the first hashmap, (Location A will give us (B, C, Q) in O(1) time).
For-each found location (B, C, Q), check if it is the final destination (Z). If so store it in the "found paths" list. Else if it doesn't already exist in "visited locations" hashmap, Recurl to step 3 now with that location as "X". (actual code below)
With this current solution, it takes forever to map all (not shortest) possible routes from "BKI" to "SIN" for this provided data.
I was wondering if there's a more effective (time-wise) way of doing it. Does anyone know of a better algorithm to find all the paths from an arbitrary position A to an arbitrary position Z ?
Actual Code for current solution:
*************************************
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.