Implement a new class for graphs with weighted edges. Either you use the ordinary Graph class as a superclass for your implementation, or you start it from scratch by following the pattern used in the ordinary Graph class. The ordinary Graph class is implemented by Michael Main which can be downloaded from his website.
After implementing the new class, provide two extra methods to implement Dijkstra’s shortest distance and shortest path algorithms as described on pages 732-743 of the third edition or pages 760-771 of the fourth edition. Please carefully read the algorithm explanation and examples in those pages so that you fully understand the whole algorithms.
The shortest path algorithms only differ from the base shortest distance algorithm in keeping a record of previous vertex for each vertex. It would be helpful to write a method for printing a path from the start vertex to a given vertex as a list of vertices on the path.
After you implement the weighted graph as requested above, write a program to help a traveler plan the shortest traveling path from one city to another. I expect your program should read a file of data containing information about a group of cities and create a graph for this group of data. The file takes the following format. In the first line of the file is the number of cities interested in the program. Then each line of the file contains three integers. The first two are the indices of cities and the third one is the distance between two cities indexed by indices (suppose that distances are integers). There is another file consisting of pairs of index (an integer) and city names (String). Doing so can make your program simpler in building graph objects. Your program needs to read in the second file too.
For example, the below may be the content of such as files:
distance.txt
5
0 3 215
1 3 731
2 4 337
4 0 280
1 2 823
Index.txt
0 town 1
1 town 2
2 town 3
3 town 4
4 town 5
Please produce your own distance and index files so that you must have at least twenty cities and specify at least 30 distances. You don’t need to provide the actual distance between known cities.
Finally your program allows the user to enter queries of the form “City1, City2” and have the program print the shortest sequence of path to travel from City1 to City2.
