EE 607 Spring 2005 Project 2

Due March 6 (mon), 10 points

Write a program that has

Input: An undirected graph (V,E) with nonnegative link weights w( ). There are
also two distinguished nodes u and v.
Output: A pair of link disjoint paths between u and v that have minimum total link weight.

The input will be a text file with the following format:

First line: An integer n, which is the number of nodes in the network. It is assumed that the nodes are numbered {1, 2, ....., n}
Second line: Two integers u and v, which are the two nodes with the link disjoint paths. The integers are separated by spaces.
Third line: An integer e, which is the number of links in the network.
The next e lines: There a line per link (x,y), which has the values x, y, and w(x,y) separated by spaces.

The output are the two paths (which is a sequence of nodes with end nodes x and y) and their lengths.

Path 1:
Length of path 1 =
Path 2:
Length of path 2 =

The executable should be labeled "disjointPath607". It has one argument, which is the name of the input file with the network topology information. It then prints out the paths and their lengths.

Example : Suppose we have a text file labeled "ring5":

5
2 3
5
1 2 6
2 3 6
3 4 6
4 5 6
5 1 6

For an example, click here.

Note that the topology is a ring of five nodes, and the link weights are 6. Also note that the disjoint paths are between the nodes 2 and 3.

Then after typing

disjoint607 ring5

The program should output the paths and their lengths. For example, the output could be

Path 1 = [2, 3]
Length Path 1 = 6
Path 2 = [3, 4, 5, 1, 2]
Length Path 2 = 24

which is displayed on the console. Note that the sequences of nodes for the paths could be listed in reverse, e.g., instead of Path 2 = [3, 4, 5, 1, 2] it could be Path 2 = [2, 1, 5, 4, 3].

What to turn in. Have your program be executable on spectra.eng.hawaii.edu Put your source code and makefile in a directory in spectra. Make sure that your makefile will compile the code and create the excecutable "disjointPath607". Tar and gzip the directory on spectra (do not use other compression methods). Then email the gzipped file to me with the email header "EE 607 Project 2".