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
