Description
Problem 1 (100 Points) Write a program that help us find the shortest path between any two buildings or point of interests in the Northeastern University campus. Utilize the Dijkstra’s Algorithm to implement the program. To carry out this task, do the following: 1. Using any drawing software (e.g., Visio), design an undirected graph using the campus map available at: https://www.northeastern.edu/campusmap/printable/campusmap15.pdf 2. Only consider the area of the campus that is located inside Huntington Avenue, Ruggles Street, Massachusetts Avenue, and the Orange Line railroad. 3. The vertices in your graph should represent the centroid of the buildings and points of interests as indicated in the map. You can also add vertices to represent some roads intersections (if needed). 4. The edges in your graph represent the roads between the vertices. The weight of an edge is determined by the distance between its two vertices. These distances can be measured utilizing Google map as explained in: https://support.google.com/maps/answer/1628031 5. Only add edges to the vertex’s direct neighbors on the map (i.e., do not include non‐ essential edges). 6. Create a text file to store your graph data, which includes: the number of vertices followed by the data of the graph edges. For each edge, provide its 7. Write your C++ program so that it starts by reading the graph text file you created in the previous step and then implement this graph using either an adjacency‐list or an adjacency‐matrix. 8. When it runs, your program will read from a user the start and end points (using numbers to refer to these points as shown in the campus map). The program will then use Dijkstra’s algorithm to provide the user with the shortest path between these two points. 9. Verify your program shortest path results with the corresponding results given by Google maps for the “walking” directions. In your homework report, include the following: o The drawing of the undirected graph you created in step (1). Have the graph labeled with the vertices numbers that match the numbers on the campus map. Also, have the edges labeled with the distances you calculated from google map. o In addition to including the screen shots of at least two sample runs of your program, include copies of the graph you created in step (1) on which you need to highlight the shortest path generated by your sample runs. Also, include screen shots of the Google map walking directions correspond to your sample runs. o Make sure to submit with your homework the text file that has your graph data. EECE7205 –‐ Homework 5 3 / 3 Programming Hints ‐ The following C++ code reads integers from a text file and stores them in an array: #include #include #include #define maxints 100 using namespace std; int main() { ifstream inf; int count = 0; int x; int list[maxints]; inf.open(“c:\\temp\\ints.txt”); if (inf.fail()) { cerr << “Error: Could not open input file\n”; exit(1); } //activate the exception handling of inf stream inf.exceptions(std::ifstream::failbit | std::ifstream::badbit); while (count < maxints) { //keep reading until reading maxints or //until a reading failure is caught. try { inf >> x; } //Check for reading failure due to end of file or // due to reading a non‐integer value from the file. catch (std::ifstream::failure e) { break; } list[count++]=x; } for(int i = 0; i < count; i++) cout << list[i] << endl; inf.close(); //Close the file at the end of your program. return 0; }
