Write a program that allows the user to read graph information from a text file that s/he specifies. Once the file is loaded, the user should be able to view all the vertices and edges (including weights) of the graph. (No need to do this graphically although youre welcome to do so if you want!) The user should also be able to select any two vertices from the graph and see the cost of the optimal path between them, as well as the optimal path itself.

Assume that the data file just lists the edges in the graph and their weights. For the example graph discussed previously, the file would look like this:

A B 0.5 A E 1.5 A D 1.2 B A 0.5 B C 0.7 C B 0.7 C E 0.5 C F 2.5 D A 1.2 D F 4.5 E A 1.5 E C 0.5 E F 0.5 F C 2.5 F D 4.5 F E 0.5

Note that each graph does not necessarily have a unique file representation. The edges could be listed in any order.

Use the following class design for the project:

Vertex class: This should include an instance variable for the vertexs name, as well as instance variables for the various quantities needed in Dijkstras algorithm (distance, visited status, and previous vertex). You can assume that all vertices in the graph will have unique names. Edge class: This should include instance variables for the start and end vertices, as well as the edges weight. Graph class: This should include a list of Vertex objects and a list of Edge objects as instance variables. You can use java.util.ArrayList or java.util.LinkedList for these lists. This class should also include the following methods: o A method that loads information from a data file o A method that runs Dijkstras algorithm using a specified start and end vertex o A toString method that includes information about the graphs vertices and edges MappingApp class: This is the client program where all user input will be made. It should contain an instance of Graph and allow the user to load a data file, view the currently loaded graph, or find the shortest path between two vertices in the currently loaded graph. As mentioned before, display both the optimal cost as well as the path itself. Implement error checking on all user inputs! This includes exception handling: possible crashes due to exceptions like InputMismatchException or FileNotFoundException should be gracefully handled. Your program should never crash due to user input. (However, you can assume that the input file is formatted correctly and contains no duplicate edges.)

(Some Background Information):

Dijkstras algorithm, developed in 1959 by the Dutch computer scientist of the same name, gives a way of computing the shortest (lowest-cost) path between any two vertices of a graph. Heres how the algorithm works. Given a graph and a starting vertex:

1. Assign each vertex a distance value. This value will represent the optimal distance between that vertex and the starting vertex. To begin with, assign the starting vertex a distance of 0 and all other vertices a distance of . 2. Mark all vertices as unvisited. 3. From the entire graph, pick the unvisited vertex with the lowest distance value. Note that the first time you do this, itll always be the starting vertex. Call this the current vertex, V. 4. Consider each of Vs unvisited neighbors (i.e., vertices that are directly accessible from V). For each of these neighbors N, compute Ns tentative distance by adding Vs distance to the weight of the edge connecting V and N. If this tentative distance is less than Ns existing distance, overwrite Ns distance with the new one. When an overwrite is performed, also record vertex V as the previous vertex of vertex N. 5. Once youve checked all of Vs unvisited neighbors, mark V as visited. V is now done and will not be involved in the algorithm any more. 6. Check if all vertices in the graph have been visited. If so, the algorithm is finished. If not, return to step 3.