COMP201 - Computer Systems and Programming - assignment3 - Solved

Computer Systems and Programming



In this assignment, you are expected to find the shortest path between two cities in a given road network using the Floyd-Warshall algorithm.

Each road in this road network connects exactly two cities, and the roads in the network have various lengths. This road network can be considered as an undirected graph since each road can be used in either direction, and has the same length in both directions. Between any two cities, there exist at least one path that connects them, though this path might not be exactly a road that directly connects the two cities. You can see an example of such a road network.

 

Given the road network above, if the question is

What is shortest path between Mordor and Narnia, and how long is it? the answer is:

Mordor - London - Gondor - Narnia

Length: 120

1. Program Description • Your program reads the road network information from a file whose name is provided as a command line argument to your program. The file name is passed to the program

as follow.

./your program input file.txt

• The input file for your program consists of lines, each of which describes a road that connects any two cities. Each line has three entries, and the entries are separated by blank spaces. The first and second entries are the names of the cities connected by the road, and the third entry shows the length of the road in kilometer.

Here is an example of a file that can be an input to your program. This program is based on the figure of road network depicted above.

Mordor London 30

London Tatooine 100

London Gondor 20

London Narnia 160

London Naboo 50

Gondor Narnia 70

Narnia Naboo 90

Naboo Asgard 60

Narnia Wakanda 40
1

2

3

4

5

6

7

8

9

Listing 1: example of input file

The file will not include the number of lines that it contains.

•    After reading the input file, the program will prompt its user to enter the names of two cities whose shortest distance and path are to be searched.

Program: Enter the cities:

User: Mordor Narnia

The names of the cities are separated by a whitespace blank. • If a shortest path is found between the two cities, the output is printed in two lines. The first line shows the sequence of cities in the path, and the second line displays the length of the path in kilometer. If there are more than one shortest path, any one of them can be a valid output. For the problem in the example, the output is:

Mordor London Gondor Narnia 120

If it was found that there exists no path, the output is a single line which is as follow.

*** NO PATH ***

•    To find the shortest path in the problem, you are expected to utilize Floyd-Warshall algorithm. This algorithm finds and calculates the length of the shortest paths between all pairs of vertices in a graph. In your code, this algorithm is executed only once. However, the shortest paths that it finds can be queried repeatedly by a entering city names in the command prompt. The algorithm is used in your code as follow.

c i t i e s  // array  of             vertices ; each array element contains a city name and its               index becomes the city ’ s numeric id

roads // array of edges ; each array element contains the ids of two c i t i e s connected directy by a road and the length of the road

 city graph // a two−dimensional array that shows the length of the shortest path between any two c i t i e s

shortest paths // a two−dimensional array that shows the direction to the shortest path between any two c i t i e s

void floydWarshall () {

 for ( int k = 0; k < c i t i e s . city count ; k++) { for ( int i = 0; i < c i t i e s . city count ; i++) {

           for     ( int       j = 0;             j < c i t i e s . city count ;            j++) {

i f (( city  graph [ i ] [ k ] == INF) | | ( city  graph [ k ] [ j ] == INF) ) { continue ;

}

          i f                     ( city graph [ i ] [ j ] > ( city graph [ i ] [ k ] + city graph [ k ] [ j ]) ) {

   city graph [ i ] [ j ] = city graph [ i ] [ k ] + city graph [ k ] [ j ] ; shortest paths [ i ] [ j ] = shortest  paths [ i ] [ k ] ;

}

}

}

}

}

int main( int            argc ,        char ∗argv [ ] )      {

             // Allocate memory regions               dynamically to        c i t i e s                  array and roads array .

// Read and parse the input           f i l e .      Insert      the          city names and ids to c i t i e s       array .

        // Insert        city           ids and road lengths               to roads array .

// Allocate memory regions dynamically to city  graph , distance , and shortest  paths arrays .

// I n i t i a l i z e the values in city  graph array with road lengths , such that the value in city  graph [ i ] [ j ] is the road length between c i t i e s i and j i f these c i t i e s are directly connected by a road . For c i t i e s

m and n that are not connected   directly by a road , the value in city  graph [m] [ n]           will       be INF,    which      is a large value       like          10M,       that

is    assumed to be       infinite . i n i t i a l i s e () ;

floydWarshall () ; while (1) {

// prompt user to enter two city names

             // print       the             shortest path between the two            c i t i e s

             // print         the length       of      the path

}

       return     0;

}
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

Listing 2: FloydWarshall Algorithm

•    A template code is provided that will help you create your final program. Please read the comments in the template code carefully before working on your code.

•    You are allowed to use ONLY dynamic memory allocation to create any array in the code.

•    When a dynamically allocated array is no longer used, the memory regions allocated for it have to be freed.

2. Work Instruction
1.    Accept the assignment link: https://classroom.github.com/a/g YOXrS3, and open the generated private Github repository.

2.    Clone the repository locally to your machine or import it to REPL.it.

3.    Work on the floyd warshall.c template code by modifying the insert to cities, printPath, and main functions to add the missing parts that are necessary to make the code work properly.

4.    To ensure that your code works correctly, you can use the provided input.txt file as an input to your program, and compare your output with the content of the expected-output.txt file. In the expected-output.txt file, there is a list of inputs and outputs that your code is supposed to produce when the input file is the input.txt file.

5.    To ensure that all dynamically allocated memory regions have been freed by the end of your code, you can use Valgrind to check if there is still unfreed allocated memory