Determine if a route exists between two stations using breadth first search and an adjacency matrix.

At a minimum, the following public functions need to be implemented:

Graph ( int routes, int stations ) Initialize total number of routes and stations

void addRoute( int from, int to, int weight )

Add route to adjacency matrix with appropriate weight

bool isRoute( int from, int to )

Return bool value indicating existence of route.

You may need to add more private/public functions in order to accomplish the task. You are allowed to statically allocate an adjacency matrix of size 100 i.e. adjMatrix[100][100]. This assumes there will never be more than 100 stations in your file.

Always know what type of graph you are using. Your program should be built to handle a weighted, directed graph.

Your program will need to read data from a file formatted as follows:

10 2

0 1 10

2 9 1

The first line of the file will contain two integers indicating the number of stations and routes. Following this first line will be n (n being equal to the total number of routes) lines representing different routes and their associated weights. For example, line 2 of the above example indicates that there is a route from station 0 to station 1 with a weight of 10. The data from this file should be used to initialize and populate your graph.

Sample:

$ cat routes.txt

10 3

0 1 10

2 9 1

1 2 5

$ ./a.out

Where would you like to start? 0

Where would you like to end? 9

Yes, you would be able to travel from station 0 to station 9.

Continue (y/n)? y

Where would you like to start? 9

Where would you like to end? 0

No, you would not be able to travel from station 9 to station 0.

Continue (y/n)? n

$