\documentclass{article}
\usepackage[a4paper]{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\newtheoremstyle{normal}{}{}{\normalfont}{}{\bfseries}{.}{ }{}
\theoremstyle{normal}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem*{theorem}{Theorem}
\newcommand{\remove}[1]{}
\newcommand{\mat}[1]{\mathbf{#1}}
\newcommand{\A}{\mat{A}}
\newcommand{\R}{\mat{R}}
\newcommand{\blank}{\mbox{--}}
\begin{document}
\title{L11 Problem Set 4}
\author{Ramana Kumar (rk436)}
\maketitle
\section{Uniqueness of Dijkstra's local optimum}
Fix the adjacency matrix $\A$, the vertex set $V$, and the source vertex $i$.
A run of Dijkstra's algorithm deals with three variables, $q$, $\R$, and $S$.
The series of values $q_2,\dots,q_{|V|}$ serves to characterize runs, since the variables $\R_k$ and $S_k$ at any iteration $k>1$ are defined in terms of $q_k$, $\R_{k-1}$, and $S_{k-1}$, and $\R_1$ and $S_1$ are always initialized the same way.
In particular $S_1=\{i\}$, $S_k=\{q_k\}\cup S_{k-1}$ for $1>This is a possible partial run because we assume $q'$ is possible, and $q''$ only differs on equal-weighted vertexes: we are assuming $\R_k(i,q_{k+1})=\dots=\R_k(i,q_{k+d+2})$ and $q'$ has a permutation of the values of $q$ in this range so they are also all equal, and Corollary~\ref{minimals constant} ensures they will stay equal, so $\R_{k+d}'(i,q_{k+d+1})=\R_{k+d}'(i,q_{k+d+2})$.
Therefore we may apply Lemma~\ref{swap} to $q'$ and $q''$ to obtain $S''_{k+d+2}=S'_{k+d+2}$ and $\R_{k+d+2}''(i,j)=\R_{k+d+2}'(i,j)$ for all $j\in V$.
By Lemma~\ref{extend}, and since $k+d+2\leq k+n+1$, we obtain $S''_{k+n+1}=S'_{k+n+1}$ and $\R_{k+n+1}''(i,j)=\R_{k+n+1}'(i,j)$ for all $j\in V$.
Now $q_{k+1}=q_{k+d+2}'=q_{k+d+1}''$, so we can apply the inductive hypothesis for the induction on $d$ to obtain $S_{k+n+1}''=S_{k+n+1}$ and $\R_{k+n+1}''(i,j)=\R_{k+n+1}(i,j)$ for all $j\in V$.
It follows that $S_{k+n+1}'=S_{k+n+1}$ and $\R_{k+n+1}'(i,j)=\R_{k+n+1}(i,j)$ for all $j\in V$ as required.
\end{proof}
\begin{lemma}\hfill\label{monster}
Let $q_1,\dots,q_k$ and $q_1',\dots,q_k'$ be partial runs, where $1\leq k\leq |V|$.
If $S_k'=S_k$ then $\R_k'(i,j)=\R_k(i,j)$ for all $j\in V$.
\end{lemma}
\begin{proof}
By induction on $k$.
In the base case we assume $1\leq k=0$, which is false, so the result follows immediately.
For the inductive case, we need to show $S_{k+1}'=S_{k+1}\implies\R_{k+1}'(i,j)=\R_{k+1}(i,j)$ for all $j\in V$, assuming $1\leq k+1\leq |V|$.
The inductive hypothesis is that $S_k'=S_k\implies\R_k'(i,j)=\R_k(i,j)$ for all $j\in V$, assuming $1\leq k\leq|V|$.
Assume $S_{k+1}'=S_{k+1}$, $1\leq k+1\leq |V|$, and $j\in V$.
If $k=0$ then we must show $\R_1'(i,j)=\R_1(i,j)$.
This holds because $\R_1'(i,i)=\R_1(i,i)=\bar{1}$ and $\R_1'(i,j)=\R_1(i,j)=\A(i,j)$ for $j\in V-\{i\}$.
Otherwise, if $k\neq 0$, we deduce $1\leq k\leq|V|$.
We have $\{q_{k+1}'\}\cup S_k'=S_{k+1}'=S_{k+1}=\{q_{k+1}\}\cup S_k$.
If $S_k'=S_k$ then since $q_{k+1}'\notin S_k'$ and $q_{k+1}\notin S_k$, we must have $q_{k+1}'=q_{k+1}$.
We get $\R_k'(i,j)=\R_k(i,j)$ from the inductive hypothesis.
If $j\in S_k$ we observe $\R_{k+1}'(i,j)=\R_k'(i,j)=\R_k(i,j)=\R_{k+1}(i,j)$.
If $j\in V-S_k$ we observe $\R_{k+1}'(i,j)=\R_k'(i,j)\oplus(\R_k'(i,q_{k+1}')\otimes\A(q_{k+1}',j))=\R_k(i,j)\oplus(\R_k(i,q_{k+1})\otimes\A(q_{k+1},j))=\R_{k+1}(i,j)$.
Otherwise, if $S_k'\neq S_k$, we must have $q_{k+1}'\neq q_{k+1}$ and both $q_{k+1}'\in S_k$ and $q_{k+1}\in S_k'$.
Since $q_{k+1}\in S_k'$, there is some $d$ such that $q_{k+1}=q_{k-d}'$ and $1\leq k-d\leq k$.
We proceed by induction on $d$.
For the base case, we have $q_{k+1}=q_k'$.
Observe that $\R_k(i,q_{k+1}')\leq\R_k(i,q_{k+1})$ by Lemma~\ref{weights increase} because $q_{k+1}'\in S_k$, and similarly $\R_k'(i,q_{k+1})\leq\R_k'(i,q_{k+1}')$.
Therefore $\R_k'(i,q_{k-d}')\leq\R_k'(i,q_{k+1}')$.
Therefore $\R_{k-d-1}'(i,q_{k-d}')\leq\R_k'(i,q_{k+1}')$.
Base case on paper.
For the inductive case, we must show $\R_{k+1}'(i,j)=\R_{k+1}(i,j)$ for all $j\in V$, assuming $q_{k+1}=q_{k-d-1}'$.
The inductive hypothesis is that $\R_{k+1}''(i,j)=\R_{k+1}(i,j)$ for all $j\in V$ whenever $q_{k+1}=q_{k-d}''$, $S_k''\neq S_k$, and $S_{k+1}''=S_{k+1}$.
\end{proof}
\begin{lemma}\hfill\label{subset}
Let $q_1,\dots,q_{k+n}$ and $q_1',\dots,q_k'$ be partial runs, where $1\leq k\leq k+n\leq|V|$.
If $S_k'\subseteq S_{k+n}$ then $\R_{k+n}(i,j)=\R_k'(i,j)$ for all $j\in S_k'$.
\end{lemma}
(A vertex's weight depends only on the set of vertexes chosen before it.)
\begin{proof}
By induction on $n$.
For the base case, we have $S_k'\subseteq S_k$.
But $|S_k'|=k=|S_k|$ so in fact $S_k'=S_k$.
Now we must show $\R_k(i,j)=\R_k'(i,j)$ for all $j\in S_k$.
<>
For the inductive case, we must show $\R_{k+n+1}(i,j)=\R_k'(i,j)$ for all $j\in S_k'$, assuming $S_k'\subseteq S_{k+n+1}$ and $1\leq k\leq k+n+1\leq |V|$.
The inductive hypothesis is that $\R_{k+n}(i,j)=\R_k'(i,j)$ for all $j\in S_k'$ as long as $S_k'\subseteq S_{k+n}$ and $1\leq k\leq k+n\leq |V|$.
Since $j\in S_k'\subseteq S_{k+n+1}$, we know $\R_{k+n+1}(i,j)=\R_{k+n}(i,j)$.
If $S_k'\subseteq S_{k+n}$, then we can use the inductive hypothesis to obtain $\R_{k+n}(i,j)=\R_k'(i,j)$ immediately.
Otherwise, if $S_k'\not\subseteq S_{k+n}$, we must have $q_{k+n+1}\in S_k'$, since that is the only element of $S_{k+n+1}\supseteq S_k'$ that is not also in $S_{k+n}$.
\remove{
By induction on $k$.
In the base case we assume $1\leq 0$, which is false, so the result is true.
For the inductive case, we must show $\R_{k+1+n}(i,j)=\R_{k+1}'(i,j)$ for all $j\in S_{k+1}'$, under the assumptions $1\leq k+1\leq k+1+n\leq |V|$ and $S_{k+1}'\subseteq S_{k+1+n}$.
The inductive hypothesis is that $\R_{k+n}(i,j)=\R_k'(i,j)$ for all $j\in S_k'$ whenever $1\leq k\leq k+n\leq|V|$ and $S_k'\subseteq S_{k+n}$.
Let $j\in S_{k+1}'$.
Then $\R_{k+1}'(i,j)=\R_k'(i,j)$.
We assume $S'_{k+1}\subseteq S_{k+1+n}$, which means $S_k'\subseteq S_{k+1+n}$.
If $j\in S_k'$
}
\end{proof}
\begin{lemma}\hfill\label{agree later}
Let $q_1,\dots,q_{|V|}$ and $q_1',\dots,q_{|V|}'$ be runs.
Suppose $S_k'=S_k$ and $\R_k'(i,j)=\R_k(i,j)$ for all $j\in V$ for some $1\leq k<|V|$.
Then there exists an $n$ satisfying $k Corollary~\ref{repeated swaps} to $q$ and $q'$ to obtain $S_{k+1+t}'=S_{k+1+t}$ and $\R_{k+1+t}'(i,j)=\R_{k+1+t}(i,j)$ for all $j\in V$.
Now since $k \ref{minimals chosen}
\end{proof}
\begin{theorem}
Let $q$ and $q'$ be runs.
Then $\R_{|V|}(i,j)=\R_{|V|}'(i,j)$ for all $j\in V$.
\end{theorem}
(Uniqueness of the output of Dijkstra's algorithm.)
\begin{proof}
Define the set of numbers $B=\{n\mid 1\leq n\leq|V|\land S_n'=S_n\land\forall{j\in V}.\;\R_n'(i,j)=\R_n(i,j)\}$.
Note that $1\in B$ and $B\subseteq\{n\mid n\leq|V|\}$, so $B$ is finite and non-empty and therefore we can take its maximum.
For contradiction, suppose $\max(B)\neq|V|$.
\remove{So $1\leq\max(B)<|V|$ and $S_{\max(B)}'=S_{\max(B)}$ and $\R_{\max(B)}'(i,j)=\R_{\max(B)}(i,j)$ for all $j\in V$.}
By Lemma~\ref{agree later}, there exists an $n\geq 1$ such that $\max(B)+n\in B$.
But this contradicts the fact that $\max(B)$ is a maximum.
Therefore we must have $\max(B)=|V|$.
Therefore $|V|\in B$, which implies $\R_{|V|}'(i,j)=\R_{|V|}(i,j)$ for all $j\in V$.
\end{proof}
\remove{
The next lemma ensures we will have ample opportunity to use Lemma \ref{swap}, since equal-weighted vertexes will be chosen for adjacent iterations.
\begin{lemma}\hfill\label{equals adjacent}
$\forall k.\; 1\leq k < |V| \land (\exists{p\in V-S_{k}}.\;\R_k(i,p)=\R_k(i,q_k))\implies \R_k(i,q_{k+1})=\R_k(i,q_k)$
\end{lemma}
(Whenever possible, the next minimal-weight vertex will have the same weight as the last.)
\begin{proof}
Assume $1\leq k < |V|$, $p\in V - S_k$, and $\R_k(i,p)=\R_k(i,q_k)$.
We know $\R_k(i,q_{k+1})=\min_{q\in V-S_k}\{\R_k(i,q)\}$.
We need to show that this minimal weight is in fact $\R_k(i,q_k)$.
We know $\R_k(i,q_k)$ is a possible weight, because $p$ has it.
If $k=1$ then $\R_k(i,q_k)=\R_1(i,i)=\bar{1}$, which is minimal since it is an annihilator for $\oplus$.
To show $\R_k(i,q_k)$ is minimal when $k>1$, let $j\in V-S_k$.
Then $\R_k(i,j)=\R_{k-1}(i,j)\oplus(\R_{k-1}(i,q_k)\otimes\A(q_k,j))$.
We compare both summands to $\R_k(i,q_k)$, which equals $\R_{k-1}(i,q_k)$ since $q_k\in S_k$.
Comparing to $\R_{k-1}(i,j)$, we observe that $\R_{k-1}(i,q_k)$ is minimal, by definition, for vertexes in $V-S_{k-1}$, and then $j$ is drawn from a subset of that.
Therefore $\R_{k-1}(i,q_k)\leq\R_{k-1}(i,j)$.
Finally, $\R_{k-1}(i,q_k)\leq\R_{k-1}(i,q_k)\otimes\A(q_k,j)$ is a consequence of RINF.
Therefore $\R_k(i,q_k)$ is minimal as required.
\end{proof}
\begin{lemma}\hfill
$\forall{knp}.\;1\leq k\leq k + n\leq|V|\land p\in V-S_k\land\R_k(i,p)=\R_k(i,q_k)\implies\R_{k+n}(i,p)=\R_k(i,q_k)$
\end{lemma}
(The weight of a minimal-weight vertex does not change.)
\begin{proof}
Assume $1\leq k \leq|V|$, $p\in V -S_k$, and $\R_k(i,p)=\R_k(i,q_k)$.
Proceed by induction on $n$.
For the base case we must show $k+0\leq|V|\implies\R_{k+0}(i,p)=\R_k(i,q_k)$, but this simplifies to one of our assumptions.
For the inductive case we must show $k+n+1\leq|V|\implies\R_{k+n+1}(i,p)=\R_k(i,q_k)$, under the assumption of the inductive hypothesis $k+n\leq|V|\implies\R_{k+n}(i,p)=\R_k(i,q_k)$.
Assume $k+n+1\leq|V|$.
It follows that $k+n\leq|V|$, so we get $\R_{k+n}(i,p)=\R_k(i,q_k)$ from the inductive hypothesis.
Proceed by cases on $p\in S_{k+n+1}$.
If $p\in S_{k+n+1}$ then $\R_{k+n+1}(i,p)=\R_{k+n}(i,p)=\R_{k}(i,q_k)$ as required.
Otherwise, if $p\in V-S_{k+n+1}$, we have $\R_{k+n+1}(i,p)=\R_{k+n}(i,p)\oplus(\R_{k+n}(i,q_{k+n+1})\otimes\A(q_{k+n+1},p))$.
\end{proof}
\begin{lemma}\hfill
Let $q_1,\dots,q_{|V|}$ and $q'_1,\dots,q_{|V|}'$ be two runs.
Suppose $S_k=S_k'$ and $\R_k(i,\blank)=\R_k'(i,\blank)$ for some $1\leq k<|V|$.
Then there exists an $n$ such that $k