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 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
- Accept the assignment link: https://classroom.github.com/a/g YOXrS3, and open the generated private Github repository.
- Clone the repository locally to your machine or import it to REPL.it.
- 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.
- To ensure that your code works correctly, you can use the provided 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.
- 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. 6. After you finish working on your code, commit and push your code to your repository.
