Java Assignment Details
The file townpairs.dat contains selected city pairs and their distances. Each line of the file contains 2 city names and a distance. Write a program to calculate the shortest path between any given city pair.
How to Solve Such Java Problems
First of all, to start finding Java assignment solution, we have to look at the requirement. What is provided to us, what is needed to do. In programming there are plenty of way to do the same thing but we need to identify which way to use in specific condition is better. Once we decide the approach we start creating a pseudo code which has the overall map of entire program. Here we need to take care of all the situations where this may fail so we need to identify all the loopholes and cover up all them before actual implementation. Then we start working on implementing actual code.
Step by Step Algorithm
- Collect city information.
- Find out shortest path and distance between two cities.
- Display path on window.
Java Assignment Solution
- Read in the city pairs and distances.
- Implement Dijkstra’s algorithm using as the edge cost the given city pair’s distance.
- Map the cities onto the window and draw the shortest path in the window between those cities. A list of (X,Y) coordinates for each of the cities can be found in the file townxy.txt.
- Display in the window the path length of the shortest path.This exercise will consider the “traveling salesperson problem” (TSP).
To read a file and store city information in the queues.
Read townxy file and set city's XY. while not townxy.isEmpty() do town = cityxy.readTown() ; townList.add(city); endwhile
Read townpair file and map them in object.
while not townpair.isEmpty() do town1 = townxy.readTown1() ; town2 = townxy.readTown2() ; dist = townxy.readTownDistance() ; edgeList.add(town1,town2,dist); endwhile
Implement Dijkstra’s algorithm.
Generate graph using node and edges. While not unSettledNodes.size() > 0 do node = getMinimum(unSettledNodes); settledNodes.add(node); unSettledNodes.remove(node); findMinimalDistances(node); endwhile
Display in the window the path
For i = 1 to pathlength do v1 = path.get(i); v2 = path.get(i + 1); g.drawString(v1.getName(), v1.getX(), v1.getY()); g.drawLine(v1.getX(), v1.getY(), v2.getX(), v2.getY()); endfor
Check more Java code samples from our experts >>>