Кратчайшие пути в графах. BFS. Dijkstra.

Задача

Дан ориентированный граф $G=(V,E)$, а также вершина $s$.
Найти длину кратчайшего пути от $s$ до каждой из вершин графа. Длина пути — количество рёбер в нём.

BFS

BFS — breadth-first search, или же поиск в ширину.

Этот алгоритм позволяет решать следующую задачу.

Алгоритм работает следующим образом.

1. Создадим массив $dist$ расстояний. Изначально $dist[s]=0$ (поскольку расстояний от вершины до самой себя равно $0$) и $dist[v]=\mathrm{\infty }$ для $v\ne s$.
2. Создадим очередь $q$. Изначально в $q$ добавим вершину $s$.
3. Пока очередь $q$ непуста, делаем следующее:
   1. Извлекаем вершину $v$ из очереди.
   2. Рассматриваем все рёбра $(v,u)\in E$. Для каждого такого ребра пытаемся сделать релаксацию: если $dist[v]+1<dist[u]$, то мы делаем присвоение $dist[u]=dist[v]+1$ и добавляем вершину $u$ в очередь.

Визуализации:

• https://visualgo.net/mn/dfsbfs

• https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/visualize/

Интуитивное понимание алгоритма

Можно представить, что мы поджигаем вершину $s$. Каждый шаг алгоритма — это распространение огня на соседние вершины. Понятно, что огонь доберётся до вершины по кратчайшему пути.

Заметьте, что этот алгоритм очень похож на DFS — достаточно заменить очередь на стек и поиск в ширину станет поиском в глубину. Действительно, оба алгоритма при обработке вершины просто записывают всех непосещенных соседей, в которые из неё есть ребро, в структуру данных, и после этого выбирает следующую вершину для обработки в структуре данных. В DFS это стек (благодаря рекурсии), поэтому мы сначала записываем соседа, идем в обрабатываем его полностью, а потом начинаем обрабатывать следующего соседа. В BFS это очередь, поэтому мы кидаем сразу всех соседей, а потом начинаем обрабатывать вообще другую вершину - ту непосещенную, которую мы положили в очередь раньше всего.

Оба алгоритма позволяют обойти граф целиком - посетить каждую вершину ровно один раз. Поэтому они оба подходят для таких задач как: * поиск компонент связности * проверка графа на двудольность * построение остова

Реализация на C++

n — количество вершин в графе; adj — список смежности

vector<int> bfs(int s) {
    // длина любого кратчайшего пути не превосходит n - 1,
    // поэтому n - достаточное значение для "бесконечности";
    // после работы алгоритма dist[v] = n, если v недостижима из s
    vector<int> dist(n, n);
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }

    return dist;
}

Свойства кратчайших путей

Обозначение: $d(v)$ — длина кратчайшего пути от $s$ до $v$.

Лемма 1. > Пусть $(u,v)\in E$, тогда $d(v)\le d(u)+1$.

Действительно, существует путь из $s$ в $u$ длины $d(u)$, а также есть ребро $(u,v)$, следовательно, существует путь из $s$ в $v$ длины $d(u)+1$. А значит кратчайший путь из $s$ в $v$ имеет длину не более $d(u)+1$,

Лемма 2. > Рассмотрим кратчайший путь от $s$ до $v$. Обозначим его как $u_1,u_2,\dots u_k$ ($u_1=s$ и $u_k=v$, а также $k=d(v)+1$).
> Тогда $\mathrm{\forall }(i<k):d(u_i)+1=d(u_{i+1})$.

Действительно, пусть для какого-то $i<k$ это не так. Тогда, используя лемму 1, имеем: $d(u_i)+1>d(u_{i+1})$. Тогда мы можем заменить первые $i+1$ вершин пути на вершины из кратчайшего пути из $s$ в $u_{i+1}$. Полученный путь стал короче, но мы рассматривали кратчайший путь — противоречие.

Корректность

Утверждение. > 1. Расстояния до тех вершин, которые были добавлены в очередь, посчитаны корректно. > 2. Вершины лежат в очереди в порядке неубывания расстояния, притом разность между кратчайшими расстояними до вершин в очереди не превосходит $1$.

Докажем это по индукции по количеству итераций алгоритма (итерация — извлечение вершины из очереди и дальнейшая релаксация).

База очевидна.
Переход. Сначала докажем первую часть. Предположим, что $dist[v]+1<dist[u]$, но $dist[v]+1$ — некорректное расстояние до вершины $u$, то есть $dist[v]+1\ne d(u)$. Тогда по лемме 1: $d(u)<dist[v]+1$. Рассмотрим предпоследнюю вершину $w$ на кратчайшем пути от $s$ до $u$. Тогда по лемме 2: $d(w)+1=d(u)$. Следовательно, $d(w)+1<dist[v]+1$ и $d(w)<dist[v]$. Но тогда по предположению индукции $w$ была извлечена раньше $v$, следовательно, при релаксации из неё в очередь должна была быть добавлена вершина $u$ с уже корректным расстоянием. Противоречие.
Теперь докажем вторую часть. По предположению индукции в очереди лежали некоторые вершины $u_1,u_2,\dots u_k$, для которых выполнялось следующее: $dist[u_1]\le dist[u_2]\le \cdots \le dist[u_k]$ и $dist[u_k]-dist[u_1]\le 1$. Мы извлекли вершину $v=u_1$ и могли добавить в конец очереди какие-то вершины с расстоянием $dist[v]+1$. Если $k=1$, то утверждение очевидно. В противном случае имеем $dist[u_k]-dist[u_1]\le 1\leftrightarrow dist[u_k]-dist[v]\le 1\leftrightarrow dist[u_k]\le dist[v]+1$, то есть упорядоченность сохранилась. Осталось показать, что $(dist[v]+1)-dist[u_2]\le 1$, но это равносильно $dist[v]\le dist[u_2]$, что, как мы знаем, верно.

Время работы

Из доказанного следует, что каждая достижимая из $s$ вершина будет добавлена в очередь ровно $1$ раз, недостижимые вершины добавлены не будут. Каждое ребро, соединяющее достижимые вершины, будет рассмотрено ровно $2$ раза. Таким образом, алгоритм работает за $O(V+E)$ времени, при условии, что граф хранится в виде списка смежности.

Неориентированные графы

Если дан неориентированный граф, его можно рассматривать как ориентированный граф с двумя обратными друг другу ориентированными рёбрами.

Восстановление пути

Пусть теперь заданы 2 вершины $s$ и $t$, и необходимо не только найти длину кратчайшего пути из $s$ в $t$, но и восстановить какой-нибудь из кратчайших путей между ними. Всё ещё можно воспользоваться алгоритмом BFS, но необходимо ещё и поддерживать массив предков $p$, в котором для каждой вершины будет храниться предыдущая вершина на кратчайшем пути.

Поддерживать этот массив просто: при релаксации нужно просто запоминать, из какой вершины мы прорелаксировали в данную. Также будем считать, что $p[s]=-1$: у стартовой вершины предок — некоторая несуществующая вершина.

Восстановление пути делается с конца. Мы знаем последнюю вершину пути — это $t$. Далее, мы сводим задачу к меньшей, переходя к нахождению пути из $s$ в $p[t]$.

Реализация BFS с восстановлением пути

// теперь bfs принимает 2 вершины, между которыми ищется пути
// bfs возвращает кратчайший путь из s в t, или же пустой vector, если пути нет
vector<int> bfs(int s, int t) {
    vector<int> dist(n, n);
    vector<int> p(n, -1);
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                p[u] = v;
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
    
    // если пути не существует, возвращаем пустой vector
    if (dist[t] == n) {
        return {};
    }

    vector<int> path;
    while (t != -1) {
        path.push_back(t);
        t = p[t];
    }
    
    // путь был рассмотрен в обратном порядке, поэтому его нужно перевернуть
    reverse(path.begin(), path.end());
    return path;
}

Проверка принадлежности вершины кратчайшему пути

Дан ориентированный граф $G$, найти все вершины, которые принадлежат хотя бы одному кратчайшему пути из $s$ в $t$.

Запустим из вершины $s$ в графе $G$ BFS — найдём расстояния $d_1$. Построим транспонированный граф $G^T$ — граф, в котором каждое ребро заменено на противоположное. Запустим из вершины $t$ в графе $G^T$ BFS — найдём расстояния $d_2$.

Теперь очевидно, что $v$ принадлежит хотя бы одному кратчайшему пути из $s$ в $t$ тогда и только тогда, когда $d_1(v)+d_2(v)=d_1(t)$ — это значит, что есть путь из $s$ в $v$ длины $d_1(v)$, а затем есть путь из $v$ в $t$ длины $d_2(v)$, и их суммарная длина совпадает с длиной кратчайшего пути из $s$ в $t$.

Кратчайший цикл в ориентированном графе

Найти цикл минимальной длины в ориентированном графе.

Попытаемся из каждой вершины найти кратчайший цикл, проходящий через неё, с помощью BFS. Это делается аналогично обычному BFS: мы должны найти расстояний от вершины до самой себя, при этом не считая, что оно равно $0$.

Итого, у нас $|V|$ запусков BFS, и каждый запуск работает за $O(|V|+|E|)$. Тогда общее время работы составляет $O(|V{|}^2+|V||E|)$. Если инициализировать массив $dist$ единожды, а после каждого запуска BFS возвращать исходные значения только для достижимых вершин, решение будет работать за $O(|V||E|)$.

Задача

Дан взвешенный ориентированный граф $G=(V,E)$, а также вершина $s$. Длина ребра $(u,v)$ равна $w(u,v)$. Длины всех рёбер неотрицательные.
Найти длину кратчайшего пути от $s$ до каждой из вершин графа. Длина пути — сумма длин рёбер в нём.

Алгоритм Дейкстры

Алгоритм Дейкстры решает приведённую выше задачу. Он работает следующим образом.

1. Создать массив $dist$ расстояний. Изначально $dist[s]=0$ и $dist[v]=\mathrm{\infty }$ для $v\ne s$.
2. Создать булёв массив $used$, $used[v]=0$ для всех вершин $v$ — в нём мы будем отмечать, совершалась ли релаксация из вершины.
3. Пока существует вершина $v$ такая, что $used[v]=0$ и $dist[v]\ne \mathrm{\infty }$, притом, если таких вершин несколько, то $v$ — вершина с минимальным $dist[v]$, делать следующее:
   1. Пометить, что мы совершали релаксацию из вершины $v$, то есть присвоить $used[v]=1$.
   2. Рассматриваем все рёбра $(v,u)\in E$. Для каждого ребра пытаемся сделать релаксацию: если $dist[v]+w(v,u)<dist[u]$, присвоить $dist[u]=dist[v]+w(v,u)$.

Иными словами, алгоритм на каждом шаге находит вершину, до которой расстояние сейчас минимально и из которой ещё не была произведена релаксация, и делает её.

Посчитаем, за сколько работает алгоритм. Мы $V$ раз ищем вершину минимальным $dist$, поиск минимума у нас линейный за $O(V)$, отсюда $O(V^2)$. Обработка ребер у нас происходит суммарно за $O(E)$, потому что на каждое ребро мы тратим $O(1)$ действий. Так мы находим финальную асимптотику: $O(V^2+E)$.

Реализация на C++

Рёбра будем хранить как pair<int, int>, где первое число пары — куда оно ведёт; а второе — длина ребра.

// INF - infinity - бесконечность
const long long INF = (long long) 1e18 + 1;

vector<long long> dijkstra(int s) {
    vector<long long> dist(n, INF);
    dist[s] = 0;
    vector<bool> used(n);
    
    while (true) {
        // находим вершину, из которой будем релаксировать
        int v = -1;
        for (int i = 0; i < n; i++) {
            if (!used[i] && (v == -1 || dist[i] < dist[v])) {
                v = i;
            }
        }
        
        // если не нашли подходящую вершину, прекращаем работу алгоритма
        if (v == -1) {
            break;
        }
        
        for (auto &e : adj[v]) {
            int u = e.first;
            int len = e.second;
            if (dist[u] > dist[v] + len) {
                dist[u] = dist[v] + len;
            }
        }
    }
    
    return dist;
}

Восстановление пути

Восстановление пути в алгоритме Дейкстры делается аналогично восстановлению пути в BFS (и любой динамике).

Дейкстра на сете

Искать вершину с минимальным $dist$ можно гораздо быстрее, используя такую структуру данных как очередь с приоритетом. Нам нужно хранить пары $(dist,index)$ и уметь делать такие операции: * Извлечь минимум (чтобы обработать новую вершину) * Удалить вершину по индексу (чтобы уменьшить $dist$ до какого-то соседа) * Добавить новую вершину (чтобы уменьшить $dist$ до какого-то соседа)

Для этого используют, например, кучу или сет. Удобно помимо сета хранить сам массив dist, который его дублирует, но хранит элементы по порядку. Тогда, чтобы заменить значение $(dis{t}_1,u)$ на $(dis{t}_2,u)$, нужно удалить из сета значение $(dist[u],u)$, сделать $dist[u]=dis{t}_2;$ и добавить в сет $(dist[u],u)$.

Данный алгоритм будет работать за $VO(logV)$ извлечений минимума и $O(ElogV)$ операций уменьшения расстояния до вершины (может быть сделано после каждого ребра). Поэтому алгоритм работает за $O(ElogV)$.

Заметьте, что этот алгоритм не лучше и не хуже, чем без сета, который работает за $O(V^2+E)$. Ведь если $E=O(V^2)$ (граф почти полный), то Дейкстра без сета работает быстрее, а если, наример, $E=O(V)$, то Дейкстра на сете работает быстрее. Учитывайте это, когда выбираете алгоритм.