% $Header: /home/rdv/quantum/genetic-paper/RCS/eaqc-paper.tex,v 1.12 2005/05/29 21:34:00 rdv Exp rdv $
% now how do I set the paper size?
% \documentclass[twocolumn]{article}

\documentclass[onecolumn,doublespace]{article}
%\documentclass{acm_proc_article-sp-no-copyright}
% \usepackage{usenix,times}
\usepackage{times}
%\usepackage{times}
\usepackage{graphics}
\usepackage{lscape}
\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsmath,amsfonts,amssymb}
%\setlength{\textwidth}{6in}
%\setlength{\textheight}{9in}
%\setlength{\oddsidemargin}{0.25in}

\pagestyle{plain}

\bibliographystyle{unsrt}

% \input{psfig}
\input{epsf}
% \epsfverbosetrue

\newcommand{\icol}[1]{% inline column vector
  \left(\begin{smallmatrix}#1\end{smallmatrix}\right)%
}

\newcommand{\irow}[1]{% inline row vector
  \begin{smallmatrix}(#1)\end{smallmatrix}%
}

\begin{document}
\title{Optimization Theory (DS2) HW\#5\\
    Shortest Path from Dijkstra to OSPF}
\maketitle
\begin{abstract}
  Is it true that OSPF and Dijkstra give the same result?
\end{abstract}

In class, I talked about two forms of Dijkstra's algorithm:
\begin{itemize}
\item The source-destination form, which starts from a source and
  searches the graph until it finds the named destination, then
  quits.
\item The all-destinations form, which builds a spanning tree that can
  be used to identify the shortest path to all possible destinations.
\end{itemize}

In this homework, we will look at the latter form and examine a
specific set of paths.  We'll use the same graph we used during class,
in Fig.~\ref{fig:graph-algos}.

The Internet's Open Shortest Path First protocol (see RFCs 2328 and
5340), which I briefly described, uses Dijkstra's algorithm.  Each
node collects information about the set of nodes and links, and the
link costs, then \emph{independently} calculates its own shortest path
spanning tree.  The Internet only works if the set of spanning trees
calculated by the nodes are consistent enough to guarantee that
packets don't get stuck in a loop somewhere.  In this homework, we are
examining that proposition.

\begin{enumerate}
\item  First, for single paths:
  \begin{enumerate}
  \item Identify the shortest path from A to E on the graph.  Although
    the edges in the original graph are undirected, this path will be
    directed.
  \item For each node in that path other than A and E, find the
    shortest (directed) path to E.  (e.g., if the A-E path is four
    hops, you will have three other paths to E, one starting at each
    of the other nodes.)  Is the set of edges in all of those paths a
    subset of the edges of the original A-E path?  Are all of the
    edges oriented in the same direction?
  \end{enumerate}
\item  Next, for trees:
  \begin{enumerate}
  \item Find the shortest path spanning tree (\emph{not} the minimum
    cost spanning tree!  Remember, they are (or can be) different.)
    for node A, including paths to all of the other nodes.  Again,
    the edges should be directed.
  \item Select a second node.  Find the shortest path spanning tree
    for it.
  \item Compare the two trees: Which portions of the trees are
    identical, which different?
  \item Construct a ``Next Hop'' table for each of the two nodes.
    Describe any similarities or differences you see.
  \end{enumerate}
\item  If the shortest path from A to some other node Z passes through
  nodes X and then Y, can it ever be the case that the shortest path
  from X to Z does \emph{not} pass through Y?  Why or why not?
\end{enumerate}

\begin{figure}
\includegraphics[width=13cm]{graph-algos}
\caption{Our nine-vertex, fourteen-edge figure from Intro to
  Algorithms.}
\label{fig:graph-algos}
\end{figure}

\end{document}
