Practice Exercise

Your task is to write a function, shortestDistance, that returns the number of edges on the shortest path between two vertices in the given graph. If there is no path between the two vertices, return -1.

Assumptions and Constraints

• The graph contains at least one vertex.
• The graph uses the adjacency list representation, and the graph struct is defined in Graph.h (and is therefore accessible from shortestDistance.c).
• Vertices are numbered from \(0\) to \(n - 1\), where \(n\) is the number of vertices.
• The source and destination vertices are between \(0\) and \(n - 1\) (inclusive), where \(n\) is the number of vertices.
• The given graph should not be modified.

Download

While in your practice exercises directory, run the following command:

unzip /web/cs2521/practice-exercises/graphs/shortestDistance/downloads/shortestDistance.zip

If you're working at home, download shortestDistance.zip by clicking on the above link and then unzip the downloaded file.

Files

Graph.c	Contains code for creating and printing a Graph
Graph.h	Contains the definition of the Graph data structure and function prototypes
Queue.c	Contains the implementation of a Queue ADT
Queue.h	Contains the interface of a Queue ADT
testShortestDistance.c	Contains the main function, which reads in a graph from standard input, calls shortestDistance and prints out the result
shortestDistance.c	Contains shortestDistance, the function you must implement
Makefile	A makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic tests
autotest	A script that uses the tests in the tests directory to autotest your solution. You should only run this after you have tested your solution manually.

Examples

./testShortestDistance
Enter number of vertices: 6
Enter number of edges: 5
Enter 5 edges in the form `v w` (no quotes):
0 1
1 2
2 3
3 4
4 5
Number of vertices: 6
Number of edges: 5
Edges:
 0: 1
 1: 0 2
 2: 1 3
 3: 2 4
 4: 3 5
 5: 4

Enter two vertices: 0 0
The shortest distance between vertices 0 and 0 is: 0
Enter two vertices: 0 3
The shortest distance between vertices 0 and 3 is: 3
Enter two vertices: 4 0
The shortest distance between vertices 4 and 0 is: 4
Enter two vertices: 1 5
The shortest distance between vertices 1 and 5 is: 4
Enter two vertices: 

./testShortestDistance
Enter number of vertices: 10
Enter number of edges: 10
Enter 10 edges in the form `v w` (no quotes):
0 1
0 2
1 3
1 6
2 9
3 4
3 5
5 7
5 9
7 8
Number of vertices: 10
Number of edges: 10
Edges:
 0: 1 2
 1: 0 3 6
 2: 0 9
 3: 1 4 5
 4: 3
 5: 3 7 9
 6: 1
 7: 5 8
 8: 7
 9: 2 5

Enter two vertices: 0 7
The shortest distance between vertices 0 and 7 is: 4
Enter two vertices: 8 2
The shortest distance between vertices 8 and 2 is: 4
Enter two vertices: 5 6
The shortest distance between vertices 5 and 6 is: 3
Enter two vertices: 

./testShortestDistance
Enter number of vertices: 10
Enter number of edges: 9
Enter 9 edges in the form `v w` (no quotes):
0 1
1 2
1 3
2 4
2 5
3 5
3 6
7 8
8 9
Number of vertices: 10
Number of edges: 9
Edges:
 0: 1
 1: 0 2 3
 2: 1 4 5
 3: 1 5 6
 4: 2
 5: 2 3
 6: 3
 7: 8
 8: 7 9
 9: 8

Enter two vertices: 6 4
The shortest distance between vertices 6 and 4 is: 4
Enter two vertices: 0 5
The shortest distance between vertices 0 and 5 is: 3
Enter two vertices: 0 8
There is no path between vertices 0 and 8
Enter two vertices: 

Testing

You can compile and test your function using the following commands:

make                                    # compiles the program
./testShortestDistance                  # tests with manual input, outputs to terminal
./testShortestDistance < input-file     # tests with input from a file, outputs to terminal
./testShortestDistance < tests/01.in    # for example, tests with input from tests/01.in
                                          # (then manually compare with tests/01.exp)

After you have manually tested your solution, you can autotest it by running ./autotest. This will run some basic tests on your program, as well as check for memory leaks/errors.

It is possible to devise your own tests by creating your own input files. See the existing input files for examples. Note that you will need to check the output yourself.