\documentstyle[12pt]{article}
\pagestyle{myheadings}
\def\headlineaux{\sc Math 220/317: Programming II/Data Structures 
\hrulefill
}
\markboth{\headlineaux}{\headlineaux}

\newcommand{\assignmentNumber}{7}
\newcommand{\outdate}{18 November 1992}
\newcommand{\duedate}{30 November 1992}

\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burt Rosenberg}}
\end{centerline}\end{titlepage}

\section*{Problem Set \assignmentNumber \hfill{\parbox{3in}
    {\small\sc\begin{flushright} Out: \outdate
     \\ Due: \duedate\end{flushright}}}}


\subsection*{Reading Assignment}
Read:
\begin{itemize}
\item Read Chapter 11, {\em Graphs.}
\item Read Appendixes A, {\em Mathematical Induction,} and
B, {\em Proof of Theorem 10--2}.
\end{itemize}

\subsection*{Goals}

Practice programming with graphs. Implementation of
a complicated algorithm, top-down design.

\subsection*{Assignment}

Implement Dijkstra's shortest-path algorithm.
The program accepts the commands,
\begin{itemize}
\item {\bf Go} --- prompts for the source vertex then runs the shortest-path
algorithm.
\item {\bf List} --- prints out the current graph.
\item {\bf Answer} --- Prints out the answer to the shortest-path problem.
For each vertex $n$ give the length of the shortest-path from the source to $n$
and the parent of $n$ along the shortest path.
\item {\bf Quit} --- exits the program.
\item $n\; m\; w$, where $n, m$  and $w$ are positive integers.
This means: make an edge of weight $w$ between vertices $n$ and $m$.
\end{itemize}

\subsection*{Example}

\begin{verbatim}
   >2 3 1
   >3 1 1
   >1 2 3
   >List
   Graph:
     Vertex  Vertex  Weight
        2       3       1
        3       1       1
        1       2       3
   >Go
   =>Enter source: 2
   Computing Shortest-paths from 2 ...
   Done.
   >Answer
   Shortest-Paths
      Vertex   Parent   Length
         1        3       2
         2        -       0
         3        2       1
   >Quit
\end{verbatim}

\subsection*{Extra Credit}
For extra credit,
implement the command {\em How?}, which prompts for a vertex $n$ then
gives the entire shortest path from the source to $n$. After
the Answer command of the previous example, the How?~command would give
this output:
\begin{verbatim}
   >How?
   =>Enter vertex: 1
          2 -> 3 -> 1  : length=2
\end{verbatim}


\end{document}
