CS2040C Assignment#5- SSSP Solved

In this assignment, we will compute the path and the distance of the shortest path between two nodes. You can assume our graphs are:

•       Directed

•       At least one node but no limitation on the number of edges.  

•       Each edge has a non-zero positive weight w > 0. Namely, there will be no edge with weight 0 or less

•       You can assume all computations are in integers.

Your graph (together with some SSSP queries) will be given in a text file. You can see there are a few files named “example?.txt” in your folder. Here is an example (example3.txt):

 

The first line will tell you the number of nodes, edges and SSSP queries. Then followed by e lines of numbers that each line represents an edge with a weight if e is the number of edges. Each edge has three number as the source, the destination and the weight of the edge. After the e lines of edges, it will be followed by q lines of queries. For each query, we will ask “what is the shortest path/distance from one node to another node?”

Skeleton Code
You will be given the following code:

•       The Graph Class: (Graph.{h,cpp})

•       The Linked List Skeleton in your Assignment 1 with iterator (simpleLinkedListTemplate.{h,cpp})

•       The driver code (main.cpp) to read in the input file and start your computations.

And you only need to submit the shortest distance function in the file Graph.cpp.  

The Graph Class (Given)
We use adjacency lists as the data structure for our graphs.  For a graph with v nodes, we will have v linked lists and each node a will have a list containing the neighbors of a, together with the weight of the edges. Please see the following diagram as an example:

 

Each of the Linked List node in the Linked List will be a pair of values of the neighboring node index and the weight of that edge. We create an auxiliary class to help you to store the pair of node number and weight and the class is called NodeWeightPair, in which is just simply a pair of integers.

Please read and understand the functions of the two classes Graph and NodeWeightPair. For example, the member function printGraph() in the Graph class will print out the graph for you:

  

The Linked List Class with Iterators (Given)
The files simpleLinkedListTemplate.{h,cpp} are the skeleton code of our Assignment 1. However, there are a few additional functions for iterating through a linked list. An example is already in Graph.cpp inside the function printGraph().

for (_al[i].start(); !_al[i].end(); _al[i].next()) 

  cout << " (" << _al[i].current().nodeIndex() << "," << _al[i].current().weight() << ")";
•       start() will place a pointer to point to the first item in the Linked List

•       next() will move the pointer to the next item

•       end() will return 1 if the current pointer is null, namely, the end of the list, otherwise, return 0.

•       current() will return the item that the pointer is pointing to currently.

                

Task 1 Compute the Shortest Distance for Each Query (50 marks)
Implement the function shortestDistance(int s, int d) in the class Graph that will return the shortest distance from the node s to the node d. If there is no path from s to d, return -1 instead. For the input file “example3.txt”, your output should be like this:

  

In this task, you probably need the priority queue. You can add into your project. But please use the same conventions in the last assignment for the heap. Please bear in mind that you are not allowed to use STL or other code that is not from you.

Task 2 Printing the Path (40 marks)
Print the path inside your function shortestDistance() if  you can find a path. Your output should be like this for “example4.txt”

  

                

Task 3 Problem Solving: Train Trips (10 marks)
Use your code to solve the following problem by creating an input file without modifying your code in Tasks 1 and 2. There are n cities and you can travel from each city to another by trains. Let’s assume that

•       In every city, the trains are operating 24 hours.  

•       Only some pairs of the cities have trains between them. And luckily, when there is a connection, trains run in both ways, aka, bidirectional. Also, each connection has a different speed limit for the trains

•       Every train will leave a city at every hour. Namely, there will be a train leaving at 12:00, 1:00, 2:00, 3:00, and so on.

•       You are provided with the information of how long the distance is between two cities, and the speed limit of the trains between the two cities, see the table below.

•       You can assume every train will gain its speed to its maximum speed, and brake, in no time.

•       And you can also transfer from train to train in no time.

Here is the distance and maximum speed for the trains between 8 cities. The first number in each cell is the distance between the two places in km. The second number is the speed limit in km per hour. Note that the matrix is symmetric and we omit the other half. Namely, the entry with Cities 0 to 1 and 1 to 0 should be the same as (200,40).

Cities     0       1       2       3       4       5       6       7 
0 
 
200,40 
 
150,30 
100,25 
 
 
 
1 
 
 
80,40 
 
 
200,100 
 
 
2 
 
 
 
 
160,40 
90,45 
240,60 
 
3 
 
 
 
 
 
 
 
 
4 
 
 
 
 
 
 
300,60 
 
5 
 
 
 
 
 
 
300,30 
360,60 
6 
 
 
 
 
 
 
270,30 
7 
 
 
 
 
Create an input file that can use your code to answer the following question: What is the shortest time (in hours) and the path to go from City 0 to City 7?