### COSC 173: Data Structures

Project 5
Spring 2004

Due: Dec 8 @ 5:10 PM
10 points

Implement one of the algorithms from lecture for finding the shortest path. The input should consist of the number of vertices, their labels, and their weights followed by pairs of vertices. The program should process standard input (i.e., cin) to create the graph and find the shortest paths between each pair of vertices. The program should output for each pair the path's length and vertices. As an example, input for the graph

might correspond to

```5
A B C D E
0 3 5 0 0
3 0 9 0 0
5 9 0 0 3
0 0 0 0 1
0 0 3 1 0
A C
D B
```
In this case, the program should output:
```path = A, C; cost = 5
path = D, E, C, A, B; cost = 12
```
Your program must work for any simple weighted graph, such as this graph representing roads in France:

For your convenience, I put the file france.dta in my top-level directory on gusun, which you can copy with the command

```cp ~maloofm/france.dta ~
```
This will copy the file into your top-level directory.

Implementing a shortest-path algorithm will probably require some containers other than the graph. You can use STL containers or containers you've implemented for previous projects.

Bonne chance!

Instructions for Electronic Submission: You must provide a working UNIX Makefile with your submission. Use the one from P1, but modify the SRCS list. At the top of the file main.cc (or the file containing the main function), place the following header comment, with the appropriate modifications:

```//
// COSC 173 Project 5
// ID: <GoCard ID>
// Instructor: Maloof
// TA: <TA's name>
//
// In accordance with the class policies and Georgetown's Honor Code,
// I certify that, with the exceptions of the class resources and those
// items noted below, I have neither given nor received any assistance
// on this project.
//
```

Although you may use any C++ compiler to develop your program, it must run under UNIX and must compile using GNU g++. You must also provide a working UNIX Makefile for your project.

If you need to include a message to your TA about your submission, then place the message in a file named README. Place the README file in the project directory p5/.

Before submitting, to reduce the size of the zip file, type 'make clean'.

To move up from the p5 directory, type

```gusun% cd ..
```

When you're ready to submit, change the name of the directory to your netid. For example, if your netid is maloofm, then rename the directory p5 by typing

```gusun% mv p5 maloofm
```
Create a zip file of the directory and its contents by typing
```gusun% zip -r p5.zip maloofm/*
```
This command creates a zip file named p5.zip by recursively (-r) copying all of the files (*) from the directory maloofm/.

To submit the zip file type

```gusun% submit -a p5 -f p5.zip
```
p5 is the name of the assignment (-a) and p5.zip is the file (-f) to be submitted for that assignment.

If the program submits the file successfully, you will receive a receipt by e-mail at the address <netid>@georgetown.edu.

```gusun% mv maloofm p5
```gusun% rm p5.zip