\Section{Алгоритм Карпа и алгоритм Джонсона}{28 сентября}{Шевченко Илья}

\Subsection{Алгоритм Карпа}

{\bf Задача:} найти цикл минимального среднего веса.

\begin{Thm}
	Величина цикла с минимальным средним весом равна $\mu=\min\limits_{v}\max\limits_{0\leq k \leq n-1}\frac{d_{n,v}-d_{k,v}}{n-k}$
\end{Thm}

\begin{Lm}
	Если вес всех рёбер уменьшить на $x$, то величина цикла с минимальным средним весом уменьшится на $x$.
\end{Lm}
Таким образом, достаточно доказать, что в если величина ответа равна нулю, то $\mu=0$. Пусть $z_v=\max\limits_{0\leq k \leq n-1}\frac{d_{n,v}-d_{k,v}}{n-k}$. Тогда $\mu=0\Leftrightarrow
\begin{cases} 
\forall v\, z_v\geq0 \\ 
\exists v \colon z_v=0 
\end{cases}
$

Докажем сначала первое. $z_v=\max\limits_k\frac{d_n-d_k}{n-k}$. $n-k>0$, поэтому чтобы определить знак достаточно рассмотреть числитель. $d_n$ - константа, поэтому $\max\limits_k\{d_n-d_k\}=d_n-\min\limits_{0\leq k \leq n-1}d_k\geq0$. Последнее неравенство верно, т.к. $\min\limits_{k=0}^{n-1}d_k$ - это кратчайший путь до вершины, а $d_n$ - какой-то путь.

Теперь докажем вторую часть. Пусть $u$ - какая-то вершина цикла длины 0. Пусть $p(u)$ - кратчайший путь в эту вершину, а количество рёбер в нём равно $k$. Пройдём от этой вершины $n-k$ рёбер вдоль цикла. Пусть мы попали в вершину $v$. Тогда $d_{n,v}=d_{u,k}$. Кроме того, кратчайший путь в вершину $u$ равен кратчайшему пути в вершину $v$. Следовательно, $\exists k\colon d_{n,v}=d_{k,v}\Rightarrow z_v=0$, ч.т.д.

Алгоритм нахождения цикла минимального веса:
\begin{enumerate}
	\item Посчитаем с помощью Форда-Беллмана матрицу $d_{n,k}$.
	\item Вычислим $\mu$.
	\item Вычтем из всех рёбер $\mu+\epsilon$.
	\item Найдём отрицательный цикл стандартным алгоритмом.
\end{enumerate}
Сложность данного алгоритм исходит из сложности ФБ и равна $\O(VE)$.

\Subsection{Алгоритм Джонсона}

{\bf Задача:} посчитать расстояние между всеми парами вершин быстрее, чем это умеет делать Флойд. В графе могут быть отрицательные рёбра

На графе с рёбрами неотрицательного веса эту задачу можно решить запустив из каждой вершины алгоритм Дейкстры за $\O(V^2\log V)$. Алгоритм Джонсона состоит из трёх шагов: 
\begin{enumerate}
	\item Сделать преобразование над рёбрами, которое делает их веса неотрицательными.
	\item Найти кратчайшие пути между всеми парами вершин на новом графе описаным выше методом.
	\item Восстановить пути в исходном графе по подсчитанным.
\end{enumerate}

\begin{Def}
	Потенциал вершины -- функция $p\colon V\rightarrow\mathbb{R}$.
\end{Def}
\begin{Def}
	Применить потенциал -- провести с весом каждого ребра $e(a,b)$ преобразование $w_e=w_e+p(a)-p(b)$.
\end{Def}
\begin{Lm}\label{Lm:pathval}
	Кратчайший путь из $a$ в $b$ увеличится на $p(a)-p(b)$.
\end{Lm}
\begin{proof}
Вес пути - это сумма весов рёбер. Заметим, что все изменения примененные к рёбрам сократятся, кроме тех, что произошли на краях.
\end{proof}
\begin{Rem}
	Кратчайшие пути исходного графа переходят в кратчайшие пути в новом графе.
\end{Rem}
Чтобы, после вычисления кратчайших путей в новом графе, получить пути в исходном нужно к для каждой пары вершин $(a,b)$ сделать $d[a,b]=d[a,b]+p(b)-p(a)$. Это прямо следует из леммы \autoref{Lm:pathval}.

\THE{Как выбрать потенциалы, чтобы новые веса рёбер были неотрицательными?}

Добавляем фиктивную вершину $s$ и из неё рёбра во все веса $0$.
Потенциал $v$ -- расстояние от фиктивной вершины $s$ до $v$.

