EECE7205: Fundamentals of Computer Engineering

Homework 5

Problem 1 (100 Points)

Write a program that will help us find the shortest path between any two buildings in the Northeastern

University Boston campus. Utilize the Dijkstra’s Algorithm to implement the program.

To carry out this task, do the following:

1. Using any drawing software, design an undirected (i.e., roads are bidirectional) graph using the

campus map available at:

https://www.northeastern.edu/campusmap/printable/campusmap15.pdf

2. Include only 16 of the buildings in the area of the campus that is located inside Huntington

Avenue, Ruggles Street, Massachusetts Avenue, and the Orange Line railroad. Select your

buildings so they are distributed evenly within that area.

3. The vertices in your graph that represent the buildings correspond to the center point of the

building. You will need also to add vertices to represent roads intersections. You need enough

intersection vertices so that none of the generated shortest paths will guide the user to walk on

a non-pedestrian area. Assign sequential numbers (0, 1, 2, … etc.) to all your graph vertices.

4. Create a text file to store your graph data, which includes: the total number of vertices followed

by the data of the graph edges. For each edge, provide its <vertex1> <vertex2> <distance>.

Here a vertex is entered as a number representing a building or an intersection. You will need

another text file to map every one of your chosen building numbers to the building character

code as shown at the bottom of the above map (e.g., SH for Shillman Hall). This mapping text

file should include in its first line, the number of buildings in your graph, which in our case is 16.

5. In your program use the graph array sequential indices (i.e., 0,1, 2, …) so that an array index

corresponds to the same vertex number stored in the graph text file.

6. 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

7. Only add edges to the vertex’s direct neighbors on the map. A direct neighbor of vertex is

another vertex on the map that represents a building or an intersection and can be reached

without passing by any other building or intersection. Also, no need to consider the internal

paths inside any building. Generally, you can utilize Google maps to help you identify which

vertices/edges to include and which ones that should not be included.

8. Write your C++ program so that it starts by reading the graph text files you created and store

the graph data in an adjacency-matrix data structures. Also read the mapping text file to an

appropriate array to map the buildings character codes to their vertices numbers in your graph.

Do not hard code the graph vertices/edges in your program as your program should work with

any graph by only changing the text file contents.

9. When it runs, the program reads from a user the start and destination buildings (using the

buildings character code). The program uses Dijkstra’s algorithm to provide the user with the

sequence of the buildings character codes and intersections numbers over the shortest path

between the start and destination. Optionally, give the intersections some meaningful codes,

like the buildings, and hence you will need to include these codes in the mapping text file.

EECE7205 – Homework 5

3 / 4

10. 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, building character codes, and optionally the intersections character codes.

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 files that have your graph data and vertices

mappings.

EECE7205 – Homework 5

4 / 4

Programming Hints

– The following C++ code reads integers from a text file and stores them in an array:

#include <iostream>

#include <fstream>

#include <stdexcept>

#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;

}

## Reviews

There are no reviews yet.