\documentclass[12pt,notitlepage]{article}
\usepackage{amsmath, graphicx, amssymb, stmaryrd, datetime, amscd, multicol, txfonts, wasysym}
\usepackage[usenames,dvipsnames]{xcolor}
% Following http://tex.stackexchange.com/a/847/22475:
\usepackage[setpagesize=false]{hyperref}\hypersetup{colorlinks,
%\usepackage{hyperref}\hypersetup{colorlinks,
  linkcolor={blue!50!black},
  citecolor={blue!50!black},
  urlcolor=blue
}

\def\yellowm#1{{\setlength{\fboxsep}{0pt}\colorbox{yellow}{$#1$}}}

\def\sheeturl{{\url{http://drorbn.net/?title=15-344}}}
\def\myurl{http://www.math.toronto.edu/~drorbn}
\def\arXiv#1{{\href{http://front.math.ucdavis.edu/#1}{arXiv:\linebreak[0]#1}}}

\def\bbR{{\mathbb R}}

\paperwidth 8in
\paperheight 10.5in
\textwidth 8in
\textheight 10.5in
\oddsidemargin -0.75in
\evensidemargin \oddsidemargin
\topmargin -0.75in
\headheight 0in
\headsep 0in
\footskip 0in
\parindent 0in
\setlength{\topsep}{0pt}
\pagestyle{empty}
\dmyydate

\begin{document}
%\setlength{\jot}{0ex}
\setlength{\abovedisplayskip}{0.5ex}
\setlength{\belowdisplayskip}{0.5ex}
\setlength{\abovedisplayshortskip}{0ex}
\setlength{\belowdisplayshortskip}{0ex}

\parbox[b]{4in}{
  \footnotesize\sheeturl
  \newline\bf
  \href{\myurl/}{Dror Bar-Natan}:
  \href{\myurl/classes/}{Classes}:
  \href{\myurl/classes/\#1516}{2015-16}:
  \href{http://drorbn.net/?title=15-344}{MAT 344 Combinatorics}:
}
\hfill\parbox[b]{3.4in}{
  \null\hfill{\LARGE\bf Dijkstra's Algorithm}
}

\vskip -3mm
\rule{\textwidth}{1pt}
\vspace{-8mm}

\begin{multicols*}{2}\raggedcolumns

\noindent{\bf Problem.} Given a connected network $G=(V,E)$; $w\colon E\to\bbR_{\geq 0}$ and two vertices $a,z\in V$, find the $w$-shortest path from $a$ to $z$.

\vskip 2mm\noindent{\bf Dijkstra's Algorithm.} Throughout, we'll have a decomposition $V=C\sqcup U$ of $V$ into two disjoint sets, $C$ for Confirmed / Confident and $U$ for Unknown, a function $m\colon V\to\bbR_{\geq 0}\cup\{\infty\}$ for ``min so far'', and a partially defined function $b\colon V\to V$ for ``backtracking''. As we run, the set $C$ will grow and the set $U$ will shrink. We stop when $z\in C$, and then $m(z)$ will be ``the time to $z$'' and $(z, b(z), b(b(z)), \ldots)$ will be the path from $a$ to $z$, going backwards.

\vskip 1mm{\bf Initialization. } Set $C\coloneqq\{a\}$, $U\coloneqq V\setminus\{a\}$, $m(a)\coloneqq 0$, and $b(a)\coloneqq\smiley$. Also, if $x$ is adjacent to $a$ set $m(x)\coloneqq w(ax)$ and $b(x)\coloneqq a$, and for all other $x$ set $m(x)\coloneqq\infty$ and $b(x)=\text{undef}$.

\vskip 1mm{\bf Iteration. } Let $x_0$ be where $m$ attains its minimum on $U$ (breaking ties arbitrarily), move $x_0$ from $U$ to $C$, and for each neighbor $y\in U$ of $x_0$, if $m(x_0)+w(x_0y)\geq m(y)$, do nothing. Else set $m(y)\coloneqq m(x_0)+w(x_0y)$ and $b(y)\coloneqq x_0$.

\def\examplescale{0.85}
\vskip 2mm{\bf Example.} Solve the shortest path problem for the network:
\[
  \def\a{$a$}
  \def\b{$b$}
  \def\c{$c$}
  \def\d{$d$}
  \def\e{$e$}
  \def\z{$z$}
  \scalebox{\examplescale}{\input{ExampleNetwork.pdf_t}}
\]

\vskip 1mm{\bf Initialization / Step 0.} Notation: $(C/U, m, b)$
\[
  \def\a{$a\colon\yellowm{(C,0,\smiley)}$}
  \def\b{$b\colon\yellowm{(U,4,a)}$}
  \def\c{$c\colon\yellowm{(U,2,a)}$}
  \def\d{$d\colon(U,\infty,?)$}
  \def\e{$e\colon(U,\infty,?)$}
  \def\z{$z\colon(U,\infty,?)$}
  \scalebox{\examplescale}{\input{ExampleNetwork.pdf_t}}
\]

{\bf Step 1.} $x_0=c$ and
\[
  \def\a{$a\colon(C,0,\smiley)$}
  \def\b{$b\colon(U,\yellowm{3,c})$}
  \def\c{$c\colon(\yellowm{C},2,a)$}
  \def\d{$d\colon(U,\yellowm{10,c})$}
  \def\e{$e\colon(U,\yellowm{12,c})$}
  \def\z{$z\colon(U,\infty,?)$}
  \scalebox{\examplescale}{\input{ExampleNetwork.pdf_t}}
\]

{\bf Step 2.} $x_0=b$ and
\[
  \def\a{$a\colon(C,0,\smiley)$}
  \def\b{$b\colon(\yellowm{C},3,c)$}
  \def\c{$c\colon(C,2,a)$}
  \def\d{$d\colon(U,\yellowm{8,b})$}
  \def\e{$e\colon(U,12,c)$}
  \def\z{$z\colon(U,\infty,?)$}
  \scalebox{\examplescale}{\input{ExampleNetwork.pdf_t}}
\]

{\bf Step 3.} $x_0=d$ and
\[
  \def\a{$a\colon(C,0,\smiley)$}
  \def\b{$b\colon(C,3,c)$}
  \def\c{$c\colon(C,2,a)$}
  \def\d{$d\colon(\yellowm{C},8,b)$}
  \def\e{$e\colon(U,\yellowm{10,d})$}
  \def\z{$z\colon(U,\yellowm{14,d})$}
  \scalebox{\examplescale}{\input{ExampleNetwork.pdf_t}}
\]

{\bf Step 4.} $x_0=e$ and
\[
  \def\a{$a\colon(C,0,\smiley)$}
  \def\b{$b\colon(C,3,c)$}
  \def\c{$c\colon(C,2,a)$}
  \def\d{$d\colon(C,8,b)$}
  \def\e{$e\colon(\yellowm{C},10,d)$}
  \def\z{$z\colon(U,\yellowm{13,e})$}
  \scalebox{\examplescale}{\input{ExampleNetwork.pdf_t}}
\]

{\bf Step 5, end.} $x_0=z$ so we are done; the minimal path length is $m(z)=13$, and the path, going backwards, is $z \overset{b}{\rightarrow} e \overset{b}{\rightarrow} d  \overset{b}{\rightarrow} b \overset{b}{\rightarrow} c \overset{b}{\rightarrow} a$.

\vskip 2mm{\bf Proof that the algorithm works.} The inductive assertion is ``after each step, for each $x\in C$ the minimal path length to $x$ is $m(x)$ and the stop before $x$ is $b(x)$; for each $x\in U$ for which $m(x)<\infty$, the minimal path length where all stops but the last are in $C$ is $m(x)$ and the stop before $x$ (in such a path) is $b(x)$''.

\vskip 2mm{\bf Efficiency estimate.} For concreteness, take $|V|=1,000,000$ and assume that the maximal degree of a vertex is 7.

Very naively, the search for $x_0$ is fast and we need about $7,000,000$ operations in total.

Less naively, the search for $x_0$ takes about $500,000$ operations, so our total is $1,000,000\times (7+500,000)$.

Cleverly, instead of a search, we maintain an ordered table of the values of $m$. Updating the table takes about $\log_2(500,000)\sim 20$ operations, so the total number of operations required is about $1,000,000\times(7+7\times 20)$, a feasible number.

\vskip 2mm{\bf Finding a minimal spanning tree.}

\vskip 1mm{\bf Kruskal's Algorithm.} Start with $T=\emptyset$; repeatedly add to $T$ the cheapest edge that does not form a circuit with edges already in $T$.

\vskip 1mm{\bf Prim's Algorithm.} Start with $T=\emptyset$; repeatedly add to $T$ the cheapest edge that connects $T$ and the complement $T^c$ of $T$.

\vfill

{\bf Read Along. } Section 4.1 and 4.2, and all of section 5.

{\bf HW5} will be on the web by midnight tonight, October 29.

{\bf No Dror office hours} on Tuesday November 3, sorry.

\end{multicols*}

\end{document}

\endinput