\Section{BFS, Dijkstra}{20 ноября}{Даниил Смирнов}

\Subsection{Рекламная пауза}
    А что мы знаем о поиске кратчайших путей?
    \begin{enumerate}[1.]
        \item Невзвешенный граф $\Rightarrow \O(V + E)$ --- BFS
        \item Взвешенный
            \begin{enumerate}[a.]
                \item $w_i \geqslant 0$ --- Дейкстра (Dijkstra):
                    \begin{enumerate}[1.]
                        \item $E ^ 2 + V$
                        \item $E \log V$ (heap)
                        \item $E + V \log V$ (Fib. heap)
                        \item $(E + V \log C)$ OR $(E + V \sqrt{\log C})$ ($w_i \in \{1 \ldots C\}$, radix heap)
                    \end{enumerate}
                \item $w_i \in \Z + \text{ Неорграф } \Rightarrow \O(V + E)$ --- Thorup (2002)
                \item $w_i \in \Z + \text{ Орграф } \Rightarrow \O(E + V \log \log V)$
                \item Нет отр. циклов - алгоритм Форда-Беллмана $(\O(VE)) \rightarrow$ алгоритм Гольдберга     
                    (1993) $(\O(E \sqrt{V} \log N))$
            \end{enumerate}
    \end{enumerate}

\Subsection{BFS}
    Ищет путь от заданной вершины $s$ до всех остальных на невзвешенном графе. На $i$-м шаге 
    рассматриваются вершины множества $A_i$ - вершины на расстоянии $i$ от $s$. \\
    Реализация: 
    \begin{enumerate}[1.]
        \item Так делать не нужно
            \begin{lstlisting}[language=c++][gobble=12]
vector<vector<int>> a(n);
a[0].push_back(s), d[s] = 0;
for (int i = 0; i < n; ++i) {
    // Calc for a[i + 1] using a[i]
}
            \end{lstlisting}
        \item На очереди
            \begin{lstlisting}[language=c++][gobble=12]
memset(d, -1, sizeof(d));
queue<int> q;
for (q.push(s), d[s] = 0; !q.empty(); ) {
    int u = q.front(), q.pop();
    for (int v: edges[u]) {
        if (d[v] == -1) {
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
}
            \end{lstlisting}
        \item Заметим, что на основе этого можно сделать Недо-DFS без рекурсии
            \begin{lstlisting}[language=c++][gobble=12]
memset(d, -1, sizeof(d));
stack<int> q;
for (q.push(s), d[s] = 0; !q.empty(); ) {
    int u = q.back(), q.pop();
    for (int v: edges[u]) {
        if (d[v] == -1) {
            p[v] = u;
            d[v] = 0;
            q.push(v);
        }
    }
}
            \end{lstlisting}
    \end{enumerate}
    Time: $\O(V + E)$

\Subsubsection{Граф кратчайших путей из $s$ в $t$}
    \begin{enumerate}[1.]
        \item $BFS(s)$
        \item оставим ребра, такие что $d[v] = d[u] + 1$
        \item $DFS\_reversed(t)$;
    \end{enumerate}

\Subsubsection{Матрица расстояний ($d[s][t]$), транзитивное замыкание ($exists\_path[s][t]$)}
    Очевидно: $\O(V \cdot (V + E))$ --- $BFS$ из каждой вершины \\
    Давайте искать замыкание чуть быстрее --- за $\O(\frac{V \cdot (V + E)}{\omega})$, где $\omega$ - машинное слово
    \begin{enumerate}[1.]
        \item bitset<N> exists\_path[N];
        \item решим для конденсации (которую построим, конечно же, за $\O(V + E)$)
        \item получен ориентированный ациклический граф, будем считать по нему динамику: $is[u] = \left(\underset{u \rightarrow v}{\cup} is[v]\right) \cup {u}$
    \end{enumerate}

\Subsubsection{Форд-Беллман}
    Испортим $BFS$ так, что он превратится в алгоритм Форда-Беллмана:
        \begin{lstlisting}[language=c++][gobble=8]
memset(d, -1, sizeof(d));
queue<int> q;
for (q.push(s), d[s] = 0; !q.empty(); ) {
    int u = q.front(), q.pop();
    for (int v: edges[u]) {
        if (d[v] == -1 || d[v] > d[u] + w[u][v]) {
            d[v] = d[u] + w[u][v];
            q.push(v);
        }
    }
}
        \end{lstlisting}

\Subsubsection{0-1-BFS ($w_i \in \{0, 1\}$)}
    Сначала обрабатываем нулевые ребра, затем единичные, то есть: \\
        $w[u][v] = 0 \rightarrow q.push\_front(v)$ \\
        $w[u][v] = 1 \rightarrow q.push\_back(v)$ \\
    $\O(V + E)$, так как мы добавим не более одного раза с каждой стороны

\Subsubsection{1-K-BFS ($w_i \in \{1, \ldots K\}$)}
    \begin{enumerate}[1.]
        \item Делим ребро длины $l$ на путь длины $l$ через фиктивные вершины и пускаем 
            по ним обычный $BFS$ ($\O(V + KE)$)
        \item $K + 1$ очередь. Последовательно рассматриваем пути длины от 0 до $(V - 1)K$. Пусть мы сейчас 
            смотрим на путь длины $d$, тогда наши очереди представляют собой очереди для $d, d + 1, \ldots, d 
            + K$. Идем по ребрам вершин, для которых ответ не больше $d$, в очереди для $d$ и закидываем 
            потомков в очереди $d + \underset{u \rightarrow v}{w}$, обновляя ответ.
    \end{enumerate}