Description

Programming Assignment # 5
Shortest path
Acknowledgement: This assignment is based on one developed by Bob Sedgewick and Kevin Wayne.
The objective of this programming assignment is to implement the Dijkstra’s algorithm for shortest path in an undirected graph. We will work with graphs in which vertices have coordinates in a Cartesian plane. There are edges between certain pairs of vertices. The graph is provided as input via a text file. The format of the text file is as follows. The first line contains the number of vertices and edges, in that order. This is followed by one line for each vertex containing the vertex numeric ID followed by its x and y coordinates. The vertex information is followed by one line for each edge. Each line in this section identified two vertices which are the endpoints of the corresponding edge.
The following input file describes the graph shown below:

Your C++ program should read the graph from the input file into an adjacency list or adjacency matrix data structure. It should then determine the shortest paths from every vertex to every other vertex. Then, the user should be prompted to enter a source and a destination vertex. The program should respond by displaying the shortest path between the corresponding vertices and its weight.