Description

Department of Computer Science
WON’T BE ACCEPTED)

In this project, you will implement Dijkstra’s algorithm to find the shortest path between two cities.

You should read the data from the given file cities.txt and then construct the shortest path between a given city (input from the user) and a destination city (input from the user).

Your program should provide the following menu and information:
1. Load cities: loads the file and construct the graph
2. Enter source city: read the source city and compute the Dijkstra algorithm (single source shortest path)
3. Enter destination city: print the full route of the shortest path including the distance between each two cities and the total shortest cost
4. Exit: prints the information of step 3 to a file called shortest_path.txt and exits the program

Grading policy:
1. Your application should have all functionalities working properly. Twenty marks will be graded for the functionality of the project;
2. The following notes will make up the remaining 10 marks of the grade:
a. There has to be adequate documentation and comments in the code (i.e., functions, loops, etc.);
b. Your code should follow the code convention (i.e., spaces, indentations, etc.); and
c. Your application should contain a menu to allow the user to select which option (s) he would like to run.

Notes and submission instructions:
1. This is individual work. It should represent your own efforts. It is fine to discuss your work and to ask your colleagues, but you are not allowed to copy/paste the work of others or give your work to anyone else. You are not allowed to post/copy from other websites and/or social media and this will be considered as cheating.
2. Any plagiarized code will not be marked.
3. Document format. Please submit only the code file (c file) containing the code of your project. Please rename it as follows:
“P4_YourStudentID_FirstNameLastName_SectionNo.c”.
4. Input/output file name. Make sure that the input/output file names are the same as in the specifications.
5. Include your full name, student ID, and section number in the beginning of your file.
6. Please do not compress the file, only the C-file is needed.
7. Files not following the convention in point 2 will not be marked.