\documentclass[12pt]{article}
\usepackage[width=16cm,height=20cm]{geometry}
\usepackage{amsmath,amssymb,mathtools}

\newcommand{\bR}{\mathbb{R}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\eqdef}{\coloneqq}
\DeclareMathOperator*{\argmin}{arg\,min}

\usepackage{amsthm}
\swapnumbers
\theoremstyle{definition}
\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem{defn}{Definition}
\newtheorem{problem}{Problem}
\newtheorem{exer}{Exercise}
\newtheorem{rem}{Remark}

\begin{document}


\begin{center}
\large\bfseries
The cheapest path between two vertices in a directed graph\\
\large\bfseries
with costs of edges depending on discrete time
\end{center}

\medskip
This is a special task for the course ``Numerical Lineal Algebra''.
The task is composed by professor Egor Maximenko (2021-03).

\subsection*{Initial data}

\begin{itemize}
\item $n\in\{1,2,\ldots\}$ is the order of the graph.
\item $T\in\{1,2,\ldots\}$ determines the discrete time interval $\{0,\ldots,T\}$
considered in the problem.
\item three-dimensional array
$C=[C_{t,j,k}]_{1\le t\le T,\ 1\le j,k\le n}$,
where $C_{t,j,k}$ is called the cost of the travel
by the oriented edge $(j,k)$
from the moment $t-1$ to the moment $t$.
\end{itemize}
In many high-level programming languages,
all initial data can be given by one three-dimensional array $C$,
which ``knowns'' its dimensions $n$, $n$, $T$.

\medskip
Obviously, in some programming languages
it is more convenient to enumerate $t,j,k$ starting with zero.
Then $C_{t,j,k}$ is the cost of the travel
by the oriented edge $(j,k)$
from the moment $t$ to the moment $t+1$.

\begin{rem}
We suppose that $C_{t,j,k}\in(-\infty,+\infty]$ for all $t,j,k$.
In some applications it is convenient to think
that $C_{t,j,k}=+\infty$ for some $t,j,k$,
which means that the edge $(j,k)$ does not exist
at the time interval from $t-1$ to $t$.
Technically, $+\infty$ may be realized as a strict upper bound of all finite sums that may appear in the analysis of this problem.
For example, the role of $+\infty$ can play the number
\[
1 + \sum_{1\le t\le T}\max_{1\le j,k\le n}C_{t,j,k}.
\]
\end{rem}

\medskip
In general, we admit \emph{loops}, i.e. edges of the form $(j,j)$.
Depending on the applications, they may have zero costs,
or positive costs (hotel fees between flights),
or negative costs (relaxation and fatigue decrease).

\medskip
If needed, we may assume $C_{t,j,k}\ge0$ for all $t,j,k$.


\subsection*{Terminology: paths and costs of the paths}

\begin{defn}
Let $t_1,t_2\in\{0,\ldots,T\}$, $t_1<t_2$,
$a,b\in\{1,\ldots,n\}$.
A \emph{path} starting at the vertex $a$ at the moment $t_1$,
and finishing at the vertex $b$ at the moment $t_2$,
is a family $p=(p_k)_{k=t_1}^{t_2}$ taking values in $\{1,\ldots,n\}$, such that
\[
p_{t_1}=a,\qquad p_{t_2}=b.
\]
We denote by $\cP(t_1,t_2,a,b)$ the set of all such paths:
\[
\cP(t_1,t_2,a,b)\eqdef
\bigl\{p\in\{1,\ldots,n\}^{\{t_1,\ldots,t_2\}}\colon\quad
p_{t_1}=a,\quad p_{t_2}=b\bigr\}.
\]
Here we have used the usual notation $Y^X$ for the set of all functions $X\to Y$.
\end{defn}

\begin{defn}
Given a path $p\in\cP(t_1,t_2,a,b)$, the total cost of the path $p$ (with respect to $C$), is defined as
\[
F_C(p) \eqdef \sum_{t=t_1+1}^{t_2} C_{t,p_{t-1},p_t}.
\]
\end{defn}

\begin{defn}
Given $t_1,t_2$ in $\{0,\ldots,T\}$ with $t_1<t_2$
and $a,b$ in $\{1,\ldots,n\}$,
\[
M(t_1,t_2,a,b)
\eqdef \min_{p\in\cP(t_1,t_2,a,b)} F_C(p).
\]
\end{defn}

\subsection*{Problems}

Here we consider only the paths starting at time $0$.
The extension to general $t_1$ and $t_2$ is trivial.

\begin{problem}\label{problem:all}
Compute $M(0,t,a,b)$ for all $t$ in $\{1,\ldots,T\}$
and all $a,b$ in $\{1,\ldots,n\}$.
\end{problem}

\begin{problem}\label{problem:ab}
Given $a,b$ in $\{1,\ldots,n\}$,
compute $M(0,T,a,b)$, i.e.,
\[
\min_{p\in\cP(0,t_2,a,b)} F_C(p).
\]
\end{problem}

The following problems are optional.

\begin{problem}\label{problem:argmin_ab}
Given $a,b$ in $\{1,\ldots,n\}$,
find a path $p$ realizing the minimum in Problem~\ref{problem:ab}.
In other words, find
\[
\argmin_{p\in\cP(0,t_2,a,b)} F_C(p).
\]
\end{problem}

\begin{problem}\label{problem:ab_freetime}
Given $a,b$ in $\{1,\ldots,n\}$, compute
\[
\min_{t_2\in\{1,\ldots,T\}} M(0,t_2,a,b).
\]
In this version, we do not fix the finishing time.
\end{problem}

\subsection*{Idea of solution}

The following statements are easy to prove formally.

\begin{prop}
Let $t\in\{1,\ldots,T\}$, $a,b\in\{1,\ldots,n\}$.
Then
\begin{equation}\label{eq:M_initial}
M(t-1,t,a,b)=C_{t,a,b}.
\end{equation}
\end{prop}

In particular,
\begin{equation}\label{eq:M_initial_0}
M(0,1,a,b)=C_{1,a,b}.
\end{equation}

\begin{prop}\label{prop:M_principal_rule}
Let $t_1,u,t_2\in\{0,\ldots,T\}$ such that $t_1<u<t_2$,
and let $a,b\in\{1,\ldots,n\}$.
Then
\begin{equation}\label{eq:M_principal_rule}
M(t_1,t_2,a,b)
=\min_{c\in\{1,\ldots,n\}}
\Bigl(M(t_1,u,a,c) + M(u,t_2,c,b)\Bigr).
\end{equation}
\end{prop}

The following proposition can be considered as a corollary from the previous two propositions.

\begin{prop}\label{prop:M_recursive}
Let $t\in\{1,\ldots,T\}$,
and let $a,b\in\{1,\ldots,n\}$.
Then
\begin{equation}\label{eq:M_recursive}
M(0,t,a,b)
=\min_{c\in\{1,\ldots,n\}}
\Bigl(M(0,t-1,a,c) + C_{t,c,b}\Bigr).
\end{equation}
\end{prop}

Obviously, the recursive rule~\eqref{eq:M_recursive}
jointly with the initial condition~\eqref{eq:M_initial_0}
yield an algorithm to solve Problem~\ref{problem:ab}.
This algorithm can be written with embedded cycles.
If one choose the way of functional programming,
then the recursive form is sufficient.

Other problems can be solved in the same manner.

An \textbf{interesting problem} is to find more efficient
solutions of these problems.

\subsection*{Write the solution in term of tropical matrix multiplication}

\begin{defn}
Let $A$ be a matrix of the size $m\times n$,
$B$ be a matrix of the size $n\times q$,
both with elements in $\bR\cup\{+\infty\}$.
Then its \emph{tropical product} $A\circ B$ is defined as
\[
A \circ B = \left[ \min_{1\le s\le n}(A_{j,s}+B_{s,k})
\right]_{j,k=1}^{m,q}.
\]
\end{defn}

\begin{exer}
Prove the principal properties of the tropical matrix multiplication.
\end{exer}

For each $t$ in $\{1,\ldots,T\}$, denote by $C_t$ the matrix
\[
C_t \eqdef \bigl[ C_{t,a,b} \bigr]_{a,b=1}^n.
\]
For each $t_1$, $t_2$ in $\{0,\ldots,T\}$ with $t_1<t_2$,
denote by $M(t_1,t_2)$ the matrix
\[
M(t_1,t_2) \eqdef \bigl[ M(t_1,t_2,a,b) \bigr]_{a,b=1}^n.
\]

\begin{exer}
Express formulas~\eqref{eq:M_principal_rule}
and~\eqref{eq:M_recursive}
in the matrix form, using the tropical matrix multiplication.
\end{exer}

\subsection*{Recommended bibliography}

\begin{itemize}
\item Descriptions of the shortest path problem
and its solutions:
the Bellman--Ford--Moore algorithm
and the Dijkstra's algorithm.

\item Descriptions of the all-pairs shortest path problem
and its solutions, including
the Floyd--Warshall algorithm
and the Johnson's algorithm.

\item Books explaining ideas of dynamic programming
(including many general books on algorithm theory).

\item Texts on tropical mathematics,
including the tropical product of matrices
and the properties of this operation.

\end{itemize}

\end{document}