\Section{Алгоритм Йена и введение в Radix Heap}{30 ноября}{Анастасия Софронова}


\Subsection{Алгоритм Йена}
\Subsubsection{Постановка задачи}

Есть взвешенный граф с неотрицательными весами рёбер, найти в нём k-тый по длине простой путь между вершинами s и t.

\Subsubsection{2-ой по длине путь}

Рассмотрим кратчайший путь между s и t. Второй по длине путь между ними своими начальными рёбрами совпадает с первым, а затем в каком-то месте появляется первое отличие. Давайте переберём ребро, в котором путь будет отличаться, т.е. по которому мы не пойдём. Назовём это ребро запрещённым. Найдём из вершины, где мы остановились, кратчайший путь до t, запретив ходить в вершины, которые были в начале пути, а также по запрещённому ребру.
\\Т.к. в кратчайшем пути максимум $V - 1$ ребро, то мы получили время работы $V \cdot Dijkstra$

\Subsubsection{k-тый путь}

Разобьём пути между s и t на классы. Один класс определяется парой: префикс пути, запрещённые рёбра. Переберём префикс, как в предыдущем пункте, получим набор классов. Выберем из каждого класса по минимальному представителю.
\\Будем хранить Heap классов. Достанем минимум (обозначим его X) и, попытавшись разными способами увеличить префикс на одно ребро, раздробим таким образом класс X на другие классы, объединение которых даёт класс X. Сделав так k раз, получим k минимальных путей.

$Time = k \cdot (V \cdot Dijkstra + \log)$
\\$Memory = k \cdot V \cdot V$ (на самом деле $k \cdot V$, т.к. нам нужны только первые k классов)

\Subsection{Введение в Radix Heap}

\Subsubsection{}

Radix Heap = k-bfs + Dijkstra + Magic,
\\и с целыми весами рёбер от 1 до k мы получаем кратчайшие пути от одной вершины за $O(E + V \log k)$

\Subsubsection{}

Здесь нам тоже нужна k + 1 очередь...

\Subsubsection{}

...и вообще стоит заметить, что 1-k bfs и Dijkstra очень похожи...

\Subsubsection{}

...и то, что кратчайшие пути за $O(E \log k)$ мы уже получаем совершенно бесплатно следующим образом: давайте в 1-k bfs выбирать следующую очередь за $\log$, храня Heap непустых очередей...

\Subsubsection{}

...а дальше получим $E + V \sqrt{k}$ с помощью sqrt-декомпозиции: разобьём очереди на $ \sqrt{k}$ блоков по $ \sqrt{k}$ очередей, пробежим циклом по блокам, затем пробежим по первому непустому.