Java: Finding Least Expensive Routes (Picture showed) Consider the problem of fi
ID: 3712141 • Letter: J
Question
Java:
Finding Least Expensive Routes (Picture showed)
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 below, 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.
if you can implement this program, provide your test ourput picture please. appreciate that.
Part 1 - Finding Least Expensive Routes (50 points) 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 below, 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 private String target private int distance; public DistanceTo (String city, int dist) targetcity; 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> 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.Explanation / Answer
The most efficient solution to this problem would be to use dynamic programmng.We first convert the distances in cost matrix form and we apply the given algorithm below.
IF it still does not satisf you comment below i will tell you the solution based on your algorithm.
import java.util.*;
class MinimumCostPath
{
/* A utility function that returns minimum of 3 integers */
private static int min(int x, int y, int z)
{
if (x < y)
return (x < z)? x : z;
else
return (y < z)? y : z;
}
private static int minCost(int cost[][], int m, int n)
{
int i, j;
int tc[][]=new int[m+1][n+1];
tc[0][0] = cost[0][0];
/* Initialize first column of total cost(tc) array */
for (i = 1; i <= m; i++)
tc[i][0] = tc[i-1][0] + cost[i][0];
/* Initialize first row of tc array */
for (j = 1; j <= n; j++)
tc[0][j] = tc[0][j-1] + cost[0][j];
/* Construct rest of the tc array */
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
tc[i][j] = min(tc[i-1][j-1],
tc[i-1][j],
tc[i][j-1]) + cost[i][j];
return tc[m][n];
}
/* Driver program to test above functions */
public static void main(String args[])
{
int cost[][]= {{1, 2, 3},
{4, 8, 2},
{1, 5, 3}};
System.out.println("minimum cost to reach (2,2) = " +
minCost(cost,2,2));
}
}
Hope it helps.Actually you should practice more on dynamic programming as fas optimisation problems come.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.