% Programming assignment 2, CSCE 235, spring 2007
% Assigned 10 April 2007; due 22 April 2007

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=6.5truein \vsize=9truein
\pdfhorigin=1truein \pdfvorigin=1truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

\headline={\hfil}
\footline={\hfil Page~\folio\hfil}

\newcount\pno
\pno=0
\def\problem{\advance\pno by1 \noindent{\bf Problem~\the\pno.} }
\def\problemno#1. {\noindent{\bf Problem~\hbox{#1}.} }
\def\solution{\nobreak\medskip\noindent{\bf Solution.} }
\def\part#1{\medskip\indent\llap{#1\enspace}\ignorespaces}
\def\mathpart#1#2\par{{%
	\abovedisplayskip=-\ht\strutbox \advance\abovedisplayskip by-\dp\strutbox %
	\abovedisplayshortskip=-\ht\strutbox \advance\abovedisplayshortskip by-\dp\strutbox %
	\part{#1}#2\par}}

\def\implies{\;\Longrightarrow\;}
\def\N{\mathord{\bf N}}  \def\Z{\mathord{\bf Z}}
\def\Q{\mathord{\bf Q}}  \def\R{\mathord{\bf R}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}

\def\squiggle{\char`\~}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{CSCE~235: Introduction to Discrete Structures}
\centerline{{\bf Programming assignment~2} (80~points)}
\centerline{Assigned Tuesday, April~10, 2007}
\centerline{Due 11:59~p.m., Sunday, April~22, 2007}

\medskip %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent You are to implement Dijkstra's algorithm for undirected graphs,
using good design, documentation, and programming style. See Section~9.6 of the
textbook for details about this algorithm.

\medbreak

\noindent{\bf Description of input}

\smallskip

\noindent The input to your program will contain zero or more graph
descriptions; each graph description will be followed by zero or more test
cases.

A graph description, which describes a connected weighted undirected graph,
will consist of several integers, separated by spaces, on one line. It will be
of the form
$$N\quad V\quad E\quad u_1\quad v_1\quad w_1\quad u_2\quad v_2\quad w_2\quad
	\ldots\quad u_E\quad v_E\quad w_E,$$
where $N$ is a graph identifier (explained below), $V$~is the number of
vertices in the graph, $E$~is the number of edges in the graph, and the
following $3E$~integers specify the edges of the graph and their weights (the
$i$th edge of the graph connects vertices $u_i$ and~$v_i$ and has
weight~$w_i$). The vertices of the graph are labeled with consecutive positive
integers from 1 to~$V$.

For example, the graph description
$${\tt1\ 6\ 7}\ \underbrace{\tt1\ 2\ 4}_{\textstyle e_1}
	\ \underbrace{\tt1\ 6\ 2}_{\textstyle e_2}
	\ \underbrace{\tt2\ 3\ 3}_{\textstyle e_3}
	\ \underbrace{\tt2\ 5\ 3}_{\textstyle e_4}
	\ \underbrace{\tt3\ 4\ 2}_{\textstyle e_5}
	\ \underbrace{\tt4\ 5\ 1}_{\textstyle e_6}
	\ \underbrace{\tt5\ 6\ 3}_{\textstyle e_7}$$
describes the graph below, where the italic numbers are labels for the vertices
and the roman (upright) numbers are weights of edges.
$$\fig{program-2.1}$$

The first number in a graph description is a graph identifier, which is simply
an integer between 1 and~1000000 (one million), inclusive. The value of this
number is not important, except that you must include it in your output (see
the next section). In particular, the graph identifiers do not need to come in
any order, and they may be repeated in an input file; in fact they may be
entirely random. The end of the input will be specified by a single zero where
otherwise there would be a graph identifier.

Your program should be able to handle all valid graph descriptions where
$1\le V\le32$, $0\le E\le2000$, and $0\le w_i\le5000$ for all~$i$. Be aware
that the input describes {\it undirected\/} graphs, so an edge may be specified
by giving its endpoints in either order. Also be aware that a graph description
may describe a graph that is not simple; you must figure out how to handle the
possibility of nonsimple graphs. However, you are guaranteed that the graphs
given as input will be connected.

Following each graph description will be one line which will contain zero or
more test cases. This line will be of the form
$$n\quad a_1\quad b_1\quad a_2\quad b_2\quad\ldots\quad a_n\quad b_n,$$
where $n$ is the number of test cases and the following $2n$~integers specify
pairs of vertices. For each pair~$(a_i,b_i)$, your program should find the
length of a shortest path between the vertices $a_i$ and~$b_i$ in the graph.

Thus, the input consists of a description of a graph, followed by several
``distances'' for your program to compute. Then comes a description of another
graph, followed by another list of distances to compute, and so on. The input
ends when there is a zero in a position that would normally be a graph
identifier.

The input will be available to your program through {\it standard input}. This
means that you can use {\tt cin} to read the input in C++, {\tt scanf}~in~C,
{\tt System.in} in Java, and the corresponding functions in other programming
languages. Please ask me if you have questions about the mechanics of reading
the input.

\medbreak

\noindent{\bf Description of output}

\smallskip

\noindent The output of your program should be presented one graph description
per line. Each line should begin with the graph identifier; this is to make it
easier for me to match up the lines of your output with the lines of the input.
For each of the test cases for this graph description, your program should
output one space (to separate the output of this test case from that of
previous test cases or the graph identifier), followed by the length of a
shortest path in the specified graph between the two vertices given in the test
case. After all of the test cases have been completed for the graph
description, your program should output a single newline. The lines of your
output should not contain leading or trailing spaces.

The output of your program should be sent to {\it standard output}. This means
that you should use {\tt cout} to produce the output in C++, {\tt printf}~in~C,
{\tt System.out} in Java, and the corresponding functions in other programming
languages.

Do not output any prompts, debugging information, or anything else other than
the results I ask for above. When your program is graded, a large input file
will be piped to your program, and the output your program produces for this
input file will be saved to an output file. This output file will be
automatically compared with a file containing the correct answers. If your
output contains prompts or other extraneous information, this comparison step
will indicate that your program produced incorrect output.

\medbreak

\noindent{\bf What to hand in}

\smallskip

\noindent Hand in all source files and a README file that explains how to
compile and run your program. It is not necessary to hand in a binary
executable. Use the Web handin system at
$$\hbox{\tt http://cse.unl.edu\slash\squiggle cse235\slash handin/}$$
to hand in your files. Instructions for using the Web handin system were
included on the back of the handout for the first programming assignment; if
you've lost this handout, you can get a copy from the course Web page.

\medbreak

\noindent{\bf Sample input}

{\smallskip\narrower\narrower\parindent=0in\tt

1 6 7 1 2 4 1 6 2 2 3 3 2 5 3 3 4 2 4 5 1 5 6 3\hfil\break
5 1 4 1 2 3 6 4 2 3 4\hfil\break
77777 6 9 1 2 2 3 1 8 2 3 6 4 6 6 4 5 5 6 5 8 1 6 14 2 5 5 3 4 3\hfil\break
12 4 5 6 2 4 4 2 3 1 6 6 1 1 4 2 5 1 5 2 4 3 4 1 2\hfil\break
235 8 7 1 2 1 2 3 6 3 4 15 4 5 20 5 6 15 6 7 6 7 8 1\hfil\break
4 1 8 3 6 7 5 2 3\hfil\break
1138 3 5 1 2 791 2 1 603 2 3 240 2 2 82 1 3 926\hfil\break
5 1 2 1 3 2 3 2 2 3 1\hfil\break
0

\smallskip}

\noindent In this example, the first line is the graph description used as an
example earlier. The second line asks for five distances in this graph: the
length of a shortest path between vertices 1 and~4, the length of a shortest
path between vertices 1 and~2, and so on. The third line is a description of a
different graph (with an arbitrary graph identifer~77777), and the fourth line
asks for 12~distances in this graph. This pattern continues; the end of the
input is specified by a single zero in place of a graph description.

\medbreak

\noindent{\bf Sample output}

{\smallskip\narrower\narrower\parindent=0in\tt

1 6 4 6 4 2\hfil\break
77777 5 13 0 6 14 14 11 5 7 9 3 2\hfil\break
235 64 50 21 6\hfil\break
1138 603 843 240 0 843

\smallskip}

\noindent The first line of this output begins with the graph identifier~1,
from the first line of the input. Then come the five distances requested in the
second line of the input. For example, the length of a shortest path between
vertices 1 and~4 is~6 (this path begins at vertex~1, passes through vertices 6
and~5, and ends at vertex~4).

\medbreak

\noindent{\bf Grading}

\smallskip

\noindent Your grade for this programming assignment will consider several
aspects of your program, including but not limited to correctness (this is
important), your choice of graph representation (see Section~9.3 of the
textbook for some ideas), adherence to these specifications, and program design
and documentation.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye