%% This LaTeX-file was created by <jcl> Tue Feb 24 16:16:39 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}


\section{Shortest path algorithms}

\begin{itemize}
\item \( G \) is a digraph 
\item \( w(e)= \) weight of edge e
\item \( P \) is a path
\item \( w(P)=\sum _{i=1}^{k-1}w(v_{i}\rightarrow v_{i+1}) \)
\item \( \delta (u,v)=min_{P:u\rightarrow v}w(P) \) = weight of minimum weight path from \( u \) to \( v \)
\end{itemize}
There are several categories of weights:

\begin{itemize}
\item \( w(e)=1 \) always (weights always the same)
\item \( w(e)\geq 0 \) always (weights always positive)
\item \( w(e)\in R \) (weights have any value)
\end{itemize}
In addition, there are 2 basic flavors of the algorithms

\begin{itemize}
\item single pair or single source 
\item all pairs
\end{itemize}
Here is a table of the algorithms which are used.

\( \begin{array}{cccc}
 & w(e)=1 & w(e)\geq 1 & w(e)\in R\\
Single & BreadthFirstSearch & Dijkstra & Bellman-Ford\\
all & BFS & Dijkstra & Johnson
\end{array} \)


\section{Rings}

A ring is defined by \( R=(S,\bigoplus ,\bigotimes ,0,1) \) where \( S \) is a set, \( \bigotimes ,\bigoplus :S^{2}\rightarrow S \) are binary operations. \( 0 \) is the identity
element of \( \bigoplus  \) and \( 1 \) the identity element of \( \bigotimes  \). Rings also obey the following
rules:

\begin{itemize}
\item \( (a\bigoplus b)\bigoplus c=a\bigoplus (b\bigoplus c) \) and \( (a\bigotimes b)\bigotimes c=a\bigotimes (b\bigotimes c) \) (associativity)
\item \( a\bigoplus b=b\bigoplus a \) (commutativity)
\item \( (a\bigoplus b)\bigotimes c=(a\bigotimes c)\bigoplus (b\bigotimes c) \) and \( a\bigotimes (b\bigoplus c)=(a\bigotimes b)\bigoplus (a\bigotimes c) \) (distributivity)
\item \( a\bigoplus 0=0\bigoplus a=a \)
\item \( a\bigotimes 1=1\bigotimes a=a \)
\item \( \exists (-a):a\bigoplus (-a)=0 \) (inverse)
\end{itemize}
A semiring must satisfy every requirement except for the last.


\subsection{ring matrices}

Given any ring a matrix ring, \( R^{n\times n}=(S^{n\times n},\bigoplus ^{n\times n},\bigotimes ^{n\times n},0^{n\times n},1^{n\times n}) \) can be defined. \( 0^{n\times n} \) is the \( 0 \) matrix and \( 1^{n\times n} \) is the
identity matrix. The addition operator is defined elementwise and the multiplication
operator is defined as: \( A^{n\times n}\bigotimes ^{n\times n}B^{n\times n}=\bigoplus _{k=1}^{n}(A_{ik}\bigotimes B_{kj}) \).


\subsection{ring examples}

\begin{itemize}
\item Minimum weight paths can be defined using a ring \( (R\cup \{\infty \},min,+,\infty ,0) \).
\item Another ring: \( (R^{+}\cup \{\infty \},max,*,0,1) \).
\item boolean ring: \( (\{0,1\},\bigvee ,\wedge 0,1) \)
\item \( (Z\cup \{\pm \infty \},min,max,+\infty ,-\infty ) \)
\end{itemize}

\subsection{Shortest path through rings}

Consider the \( min,+ \) ring above. Construct an \( n\times n \) ring from it. Assign the weights,
\( A_{ij}=\begin{array}{ccc}
w_{ij} & if & (v_{i},v_{j})\in E\\
0 & if & i=j\\
\infty  & else & 
\end{array} \)


\paragraph{Claim: \protect\( (A^{k})_{ij}=min_{P:\#P\leq k}w(P)\protect \) (the ij entry is the minimal path for all paths of length less than
k)}

To compute all pairs shortest paths, calculate \( A^{n-1} \). 


\subsection{timing analyses}

The simplest way to calculate this is by multiply \( A \) together \( n-1 \) times which has
cost \( O(n^{4}) \). This can be cut to \( O(n^{3}log(n)) \) by doing the multiplications in a more clever order.

\end{document}