Cities Dijkstra

In this problem you will implement Dijkstra's algorithm to find shortest paths between pairs of cities on a map. We are providing a GUI that lets you visualize the map and the path your algorithm finds between two cities.

(The files(attached below) contain the GUI, a graph implementation, and data files representing a map. The file cityxy.txt contains a list of citis and their (X,Y) coordinates on the map. These are the vertices in the graph. The file citypairs.txt lists direct, connections between pairs of cities. These links are bidirectional, if you can from NewYork to Boston, you can get from Boston to NewYork. These are the edges of the graph.)

• The program Display should bring up a window and display the map. You will notice that clicking on "Compute All Euclidean Distances" does nothing and that "Draw Dijkstra's Path" will throw a null pointer exception on the terminal. You will have to implement these methods yourself.
• You will not have to modify these classes (Vertex.java and Edge.java), which represent the vertices and edges of a graph.
• You will only have to modify Dijkstra.java, which represents a graph and will contain your implementation of Dijkstra's algorithm. You will need to use the instance variable vertexNames, which contains a mapping from city names to Vertex objects after the graph is read from the data files. The main method of Dijkstra illustrates how the class is used by the GUI and might be useful for testing your implementation on the command line.

a. Implement the method computeAllEuclideanDistances() which should compute the euclidean distance between all cities that have a direct link and set the weights for the corresponding edges in the graph. Once this works correctly, the correct distances should be displayed in the GUI when clicking on "Compute All Euclidean Distances".

b. In the method doDijkstra(String s), implement Dijkstra's algorithm starting at the city with name s. Use the distances associated with the edges. The method should update the distance and prev instance variables of the Vertex objects. You do not have to use a priority queue to store vertices that still need to be visited. Instead, keep these vertices on a list and scan through the entire list to find the minimum. We are making this simplification (at the expense of runtime) because java.util.PriorityQueue does not support the decreaseKey operation.

c. Implement the method getDijkstraPath(String s, String t), which first calls doDijstra(s) and then uses the distance and prev instance variables of the Vertex objects to find the shortest path between s and t. The resulting path should be returned as a list of Edge objects. Once this works correctly, you should be able to compute and display paths in the GUI.