Programming problems (optional)

Due Apr 27
Trip

You are planning a trip to several cities. Build a program to compute the optimal route for the trip by minimizing the total distance of travelling.

The program should be initiated from the command line with a map and query file:

java Trip [map] [query]
The map file is of the same format as in Dijkstra, the last programming assignment. The query file contains a single line of input in the form of:
A B C ...
where each token is a city that you plan to visit. The first city in the query is your starting as well as ending point of the trip. The rest of the cities can be visited in any order. You are guaranteed that the number of tokens in a query is no more than 6.

Your program should compute and print on the screen

  1. (if exist) the optimal ordering of cities to visit which can minimize the total distance of traveling
  2. (if exist) the detailed routes to travel between each pair of intermediate cities on the trip
If no such routes exist (one or more cities are not reachable from the starting point), simply print:
No route exists for the trip

Sample map file: 

ashburn lakecity 130
ashburn macon 84
atlanta birmingham 146
atlanta macon 84
atlanta montgomery 161
birmingham montgomery 90
birmingham tuscaloosa 58
dallas houston 239
daytonabeach jacksonville 93
daytonabeach orlando 55
jacksonville lakecity 64
jacksonville savannah 139
lakecity ocala 83
lakecity tallahassee 111
macon savannah 165
mobile montgomery 170
mobile tallahassee 243
ocala orlando 80

Smple query file: 

birmingham orlando savannah mobile tuscaloosa

Sample output: 

birmingham-savannah-orlando-mobile-tuscaloosa-birmingham (1575 miles)
        birmingham-atlanta-macon-savannah (395 miles)
        savannah-jacksonville-daytonabeach-orlando (287 miles)
        orlando-ocala-lakecity-tallahassee-mobile (517 miles)
        mobile-montgomery-birmingham-tuscaloosa (318 miles)
        tuscaloosa-birmingham (58 miles)

The first line of output gives the optimal ordering of cities starting and ending at birmingham as well as the total distance of the trip. Each following line gives the detailed route between each consecutive pair of intermediate cities and their corresponding traveling distance. The resulting routes are illustrated in the figure above, where all destination cities are marked in red, and all the routes are in bold. Note that the trip must lead back to the starting point (you must go home) and the rest of the cities can be visited in any order.

Submission and grading: I will collect your source code in lab using a USB key on the due date. You need to comment your code intensively and document all the algorithm level decisions and analysis in a separate report (txt file is fine). Your solution will be graded on both your program and your documentation.