Ryerson Crest Ryerson Header

MTH 607 Graph Theory Assignment 2

General

In this part you must implement a Breadth First Search of a weighted (di)graph G which finds the minimum weight path between two vertices. Such an algorithm is given in the Algorithms Handout. This algorithm will have to be modified to deal with weighted edges.

Input

The input will be a weighted digraph. (See the preamble for information on how the graph should be input and its format.)

The function read_graph actually reads two integers from the end of the input file, if they exist. These two integers are stored as the variables source and sink defined in graphio.h.

If there are no integers at the end of the input file, the default is the first vertex (0) for the source and the last vertex (n-1) for the sink. If only one integer is given it is assumed to be the source.

Examples

Here are some examples of some input files, the graph is P3:

3
0 1 0
1 0 1
0 1 0
2 1
3
0 1 0
1 0 1
0 1 0
0 1
3
0 1 0
1 0 1
0 1 0
2
3
0 1 0
1 0 1
0 1 0
source = 2, sink = 1 source = 0, sink = 1 source = 2, sink = 0 source = 0, sink = 2

Your routine should find a minimum weight path from source to sink.

Name

Your submitted file should be named shortest.c

Output

Your program should output a minimum weight path via write_graph, using the provided file handle file_out which is set by parse_args().

write_graph(path, file_out, n)

where path is the adjacency matrix of your minimum weight path from source to sink.

Return Value

Your program should return the length (in edges) of the shortest path found.

A return value of 0 indicates that there is no source sink path. In this case no output should be produced.

Maintained by: P. Danziger, March 2008