Use Dijkstra's algorithm discussed in class for finding the shortest distances between cities. In your project report, please discuss the data structures you used for the graph and dijkstra's algorithm. You will also need to analyze the time complexity of your program with your selected data structures Failure to follow these instructions, will result in penalties.

For this assignment, you will be provided with two data files:
1. City.dat This is a CSV text file with informations about cities. Each line is a city. Cities are sorted by the city code.
Columns: Number, City_ Code(2 letters), Full_City_Name,
Population, Elevation.
2. Road.dat This is a CSV text file with information about the connections between two cities. The cities are numbered by the city code provided in
the first file (City dat)
Columns: From_City, To_City, Distance
Your task is to build a program that first reads in the city and road information from the files, and presents a menu to the user with the following options:
1. Print City Info Let the user of this program enter a city code and your program should print out the city information (the whole record).
2. Find the connection between two cities Get two city codes as input from the user and find the shortest distance between two cities.
3. Insert a road (edge) between two cities the user will be asked to enter the two city codes and its distance
Note: that if a pair of city codes already exists or if the city code doesn't exist, print out a warning message
4. Delete a road (edge): the user will be asked to enter two city codes for this road.
Note: That if the road entered doesn't exist, print out a warning message.
5. Exit: Exit the program

Please submit a screenshot of the running output of your program. Please submit a zip file containing your code to blackboard You must also submit a project report (just like project 1 and 2). You must document your hardships, any findings, and overall any observations you had about the project. You must also be sure to analyze your implementation (ex. How did you represent the graph structure?) and report the time complexity of finding the shortest path between two cities given your implementation

Sample Output (the user inputs are underlined):
% java Project3
Command? H
Q Query the city information by entering the city code.
D Find the minimum distance between two cities.
Insert road by entering two city codes and distance
R Remove an existing road by entering two city codes.
H Display this message.
E Exit.
Command? Q
City code: LV
12 LV LEE VINING 8390 5983
Command? D
City codes: CHPM
The minimum distance between CHINO HILLS and POMONA is 143 through the route: CH, xxx, - XXX,
Command? !
City codes and distance: GG BO 100
You have inserted a road from GARDEN GRPVE to BOSSTOWN with a distance of 100.
Command? B
City codes: KV MP
The road from KERNVILLE and MOUNTAIN PASS doesn't exist
Command? El
Do not use pointer, reference.
Most important part use Dijkstra's algorithm.
Make it simple. Do not use any higher level language.
Please answer from submission part (time complexity)

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.util.*;

* Map Program which allows for interactive
* usage of cities and roads, finding
* distances, inserting and removing roads.
public class MapProgram {

// Field which stores all cities
private ArrayList<City> cities;
// Field which stores all roads
private ArrayList<Road> roads;

// Constructor accepting city dat file and road dat file
public MapProgram(String cityFile, String roadFile) {
    // Parse cities from city dat file line by line
    cities = new ArrayList<City>();
    try {
      BufferedReader br = new BufferedReader(new FileReader(cityFile));
      for(String line; (line = br.readLine()) != null; ) {
    } catch (Exception e) {
    // Parse roads from road dat file line by line
    roads = new ArrayList<Road>();
    try {
      BufferedReader br = new BufferedReader(new FileReader(roadFile));
      for(String line; (line = br.readLine()) != null; ) {
    } catch (Exception e) {

// Method to convert city code to city number
private int cityCodeToNumber(String code) {
    for (City c: cities) {
      if (c.code.equals(code)) {
       return c.number;
    return -1;

// Method to convert city number to city code
private String cityNumberToCode(int number) {
    for (City c: cities) {
      if (c.number == number) {
       return c.code;
    return "";

By purchasing this solution you'll be able to access the following files:
Solution.docx and

50% discount

$70.00 $35.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats