\Section{Алгоритмы Флойда и Беллмана-Форда}{23 ноября}{Никита Сазанович}
\Subsection{Алгоритм Флойда}

Алгоритм Флойда состоит в том, чтобы найти матрицу $d[a,b]$ -- минимальный путь от вершины $a$ до вершины $b$. Алгоритм позволяет присутствовать в графе ребрам с отрицательными весами, но не циклам отрицательного веса. Чаще всего код алгоритма выглядит следующим образом:
\begin{lstlisting}
for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            relax(d[i, j], d[i, k] + d[k, j]);
\end{lstlisting}

Предварительно, нужно заполнить $d$ бесконечностями, ячейки главной диагонали 0 и инициализировать матрицу данными нам ребрами.

Сложность алгоритма $\O(V^3)$, где $V$ - количество вершин в графе.

Покажем его корректность. Для этого рассмотри вот такую матрицу: $d[k, a, b]$ - минимальный путь от $a$ до $b$, в котором в качестве промежуточных вершин могут быть вершины от 0 до $k-1$. Изначально $d[0, a,b]=w_{a,b}$, то есть, вес ребра между $a$ и $b$ или бесконечности, если такового нет. Переход делаем следующим образом: $d[k+1,a,b]=min(d[k, a, b], d[k, a, k] + d[k, k, b])$. Действительно, когда мы позволяем вершине $k$ быть промежуточной, мы можем либо не взять ее(первый переход), либо взять(второй переход). Убрав параметр $k$ мы получим первоначальный вид алгоритма. Мы можем так поступить, ведь единственная проблема, с которой мы можем столкнуться - прохождение по вершине $k$ несколько раз, но нам это не выгодно.

\Subsection{Алгоритм Флойда и восстановление пути}

Для этого будем считать вспомогательный массив - $p[a, b]$, а именно: какую вершину мы брали в качестве промежуточной, когда обновляли ответ для $d[a, b]$?
\begin{lstlisting}
for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (d[i, j] > d[i, k] + d[k, j]) {
                d[i, j] = d[i, k] + d[k, j];
                p[i, j] = k;
            }
\end{lstlisting}

Процедура восстановления ответа выглядит следующим образом:
\begin{lstlisting}
void restore_path(int a, int b)  {
    if (p[a, b] == -1) { //edge
        cout << a << " ";
        return;
    }
    restore_path(a, p[a, b]);
    restore_path(p[a, b], b);
}
\end{lstlisting}

Для корректности рекурсии покажем, что в итоге получается простой путь и  рекурсия не зацикливается. 

\noindent
1) Пусть путь не простой. Докажем по индукции корректность. Пусть неверно для какого-либо пути $(k, a, b)$. Тогда обозначит за $x$ вершину, которая содержится и в пути от $a$ до $k$, и от $k$ до $b$($x$ не равна $k$). Заметим, что цикл $x \rightarrow k \rightarrow x$ неотрицательного веса, а следовательно путь $a \rightarrow x \rightarrow b$ не хуже, чем имеющийся. Также промежуточная вершина $x$ меньше $k$, и поэтому мы бы нашли этот путь ранее.

\noindent
2) Рекурсия не зацикливается, так как длина подзадач строго уменьшается.

Таким же образом можно восстанавливать и отрицательный цикл. Отрицательный цикл появляется, когда в какой-либо момент времени $d[a,a]$ становится меньше нуля. Это примем без доказательства.

\Subsection{Алгоритм Флойда и транзитивное замыкание}

Тривиальный алгоритм за $\O(V^3)$:
\begin{lstlisting}
for (auto e : edges)
    is[e.first][e.second] = true;
for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            is[i, j] |= is[i, k] && is[k, j];
\end{lstlisting}

Можно написать это же с bitset-ом и получить алгоритм за $\O(\frac{V^3}{\omega})$, где $\omega$ - размер машинного слова.
\begin{lstlisting}
bitset<n> is[n];
for (auto e : edges)
    is[e.first].set(e.second, 1);
for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++) 
        if (is[i, k])
            is[i] |= is[k];
\end{lstlisting}

\Subsection{Алгоритм Беллмана-Форда}

$d_1[k, b]$ - это min по путям от вершины $s$ до $b$, состоящим ровно из $k$ ребер. Изначально $d_1[0, s]=0, d_1[0, b \ne s]=\infty$. Переход: $d_1[k, b]=\min\limits_{e : a->b}(d_1[k - 1, a] + w_e)$. Но нам хотелось бы иметь min по путям не только из ровно $k$ ребер, а и по тем, количество ребер которых меньше. Такова мотивация для введения $d_2[k, b]=min(d_1[k, b], d_2[k - 1, b])$. Убрав параметр $k$, получаем знакомый всем вид этого алгоритма:
\begin{lstlisting}
for (int k = 0; k < n - 1; k++) {
    for (e : a -> b) 
        if (d[b] > d[a] + w_e) {
            d[b] = d[a] + w_e;
            p[b] = e;
        }
}
\end{lstlisting}

Мы также поддерживаем массив $p[x]$ - предыдущая вершина на пути от $x$ до $s$. 
Сложность алгоритма $\O(VE)$.

\Subsection{Алгоритм Беллмана-Форда и break}

Заметим, что мы сделаем следующую итерацию впустую, если у нас на текущей ничего не улучшилось. Эта наталкивает на мысль о переменной-индикаторе. 
\begin{lstlisting}
bool RUN = true;
for (int k = 0; k < n - 1 && RUN; k++) {
    RUN = false;
    for (e : a -> b) 
        if (d[b] > d[a] + w_e) {
            d[b] = d[a] + w_e;
            p[b] = e;
            RUN = true;
        }
}
\end{lstlisting}

Мы получили время работы $\O(kE)$, где $k$ - длина максимального по количеству ребер кратчайшего пути.

\Subsection{Алгоритм Беллмана-Форда и random\_shuffle()}

Теория вероятности утверждает, что если сделать $random\_shuffle()$ ребер перед выполнением алгоритма, то мы получим время работы $\O(\frac{k}{2}E)$.
Интуитивное объяснение этому феномену в том, что нам с очень большой вероятностью повезет и мы за одну итерацию будем выкидывать сразу два ребра кратчайшего пути. Код при этом остается таким же, как и в предыдущем пункте.

\Subsection{Алгоритм Беллмана-Форда и очередь}

Понаблюдав за поведением предыдущих реализаций алгоритма, можно осознать, что зачастую он пытается улучшать точно такую же пару вершин, как и на предыдущей итерации, хотя значения на концах этого ребра не менялись. Напрашивается введение множеств $A_i$ - множество всех вершин, которые были улучшены на итерации $i$. Как и в алгоритме $BFS$ эти множества удобно хранить в очереди. 
\begin{lstlisting}
while (q.size()) {
    int a = q.front();
    q.pop();
    in[a] = false;
    for (e : a -> b) 
        if (d[b] > d[a] + w_e) {
            d[b] = d[a] + w_e;
            p[b] = e;
            if (!in[b]) {
                q.push(b);
                in[b] = true;
            }
        }
}
\end{lstlisting}

Массив $in[v]$ хранит информация о присутствии вершины $v$ в очереди и позволяет не добавлять вершину на рассмотрение, если она уже лежит в очереди. Примечательно, что на случайных графах эта реализация алгоритма Беллмана-Форда работает за линейное время.

