Дан ориентированный граф \(G = (V, E)\), а также вершина \(s\).
Найти длину кратчайшего пути от \(s\) до каждой из вершин графа. Длина пути — количество рёбер в нём.
BFS — breadth-first search, или же поиск в ширину.
Этот алгоритм позволяет решать следующую задачу.
Алгоритм работает следующим образом.
Визуализации:
https://visualgo.net/mn/dfsbfs
https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/visualize/
Можно представить, что мы поджигаем вершину \(s\). Каждый шаг алгоритма — это распространение огня на соседние вершины. Понятно, что огонь доберётся до вершины по кратчайшему пути.
Заметьте, что этот алгоритм очень похож на DFS — достаточно заменить очередь на стек и поиск в ширину станет поиском в глубину. Действительно, оба алгоритма при обработке вершины просто записывают всех непосещенных соседей, в которые из неё есть ребро, в структуру данных, и после этого выбирает следующую вершину для обработки в структуре данных. В DFS это стек (благодаря рекурсии), поэтому мы сначала записываем соседа, идем в обрабатываем его полностью, а потом начинаем обрабатывать следующего соседа. В BFS это очередь, поэтому мы кидаем сразу всех соседей, а потом начинаем обрабатывать вообще другую вершину - ту непосещенную, которую мы положили в очередь раньше всего.
Оба алгоритма позволяют обойти граф целиком - посетить каждую вершину ровно один раз. Поэтому они оба подходят для таких задач как: * поиск компонент связности * проверка графа на двудольность * построение остова
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) \leq 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\)).
> Тогда \(\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 \neq 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] \leq dist[u_2] \leq \dots \leq dist[u_k]\) и \(dist[u_k] - dist[u_1] \leq 1\). Мы извлекли вершину \(v = u_1\) и могли добавить в конец очереди какие-то вершины с расстоянием \(dist[v] + 1\). Если \(k = 1\), то утверждение очевидно. В противном случае имеем \(dist[u_k] - dist[u_1] \leq 1 \leftrightarrow dist[u_k] - dist[v] \leq 1 \leftrightarrow dist[u_k] \leq dist[v] + 1\), то есть упорядоченность сохранилась. Осталось показать, что \((dist[v] + 1) - dist[u_2] \leq 1\), но это равносильно \(dist[v] \leq dist[u_2]\), что, как мы знаем, верно.
Из доказанного следует, что каждая достижимая из \(s\) вершина будет добавлена в очередь ровно \(1\) раз, недостижимые вершины добавлены не будут. Каждое ребро, соединяющее достижимые вершины, будет рассмотрено ровно \(2\) раза. Таким образом, алгоритм работает за \(O(V+ E)\) времени, при условии, что граф хранится в виде списка смежности.
Если дан неориентированный граф, его можно рассматривать как ориентированный граф с двумя обратными друг другу ориентированными рёбрами.
Пусть теперь заданы 2 вершины \(s\) и \(t\), и необходимо не только найти длину кратчайшего пути из \(s\) в \(t\), но и восстановить какой-нибудь из кратчайших путей между ними. Всё ещё можно воспользоваться алгоритмом BFS, но необходимо ещё и поддерживать массив предков \(p\), в котором для каждой вершины будет храниться предыдущая вершина на кратчайшем пути.
Поддерживать этот массив просто: при релаксации нужно просто запоминать, из какой вершины мы прорелаксировали в данную. Также будем считать, что \(p[s] = -1\): у стартовой вершины предок — некоторая несуществующая вершина.
Восстановление пути делается с конца. Мы знаем последнюю вершину пути — это \(t\). Далее, мы сводим задачу к меньшей, переходя к нахождению пути из \(s\) в \(p[t]\).
// теперь 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\) до каждой из вершин графа. Длина пути — сумма длин рёбер в нём.
Алгоритм Дейкстры решает приведённую выше задачу. Он работает следующим образом.
Иными словами, алгоритм на каждом шаге находит вершину, до которой расстояние сейчас минимально и из которой ещё не была произведена релаксация, и делает её.
Посчитаем, за сколько работает алгоритм. Мы \(V\) раз ищем вершину минимальным \(dist\), поиск минимума у нас линейный за \(O(V)\), отсюда \(O(V^2)\). Обработка ребер у нас происходит суммарно за \(O(E)\), потому что на каждое ребро мы тратим \(O(1)\) действий. Так мы находим финальную асимптотику: \(O(V^2 + E)\).
Рёбра будем хранить как 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, который его дублирует, но хранит элементы по порядку. Тогда, чтобы заменить значение \((dist_1, u)\) на \((dist_2, u)\), нужно удалить из сета значение \((dist[u], u)\), сделать \(dist[u] = dist_2;\) и добавить в сет \((dist[u], u)\).
Данный алгоритм будет работать за \(V O(log V)\) извлечений минимума и \(O(E log V)\) операций уменьшения расстояния до вершины (может быть сделано после каждого ребра). Поэтому алгоритм работает за \(O(E log V)\).
Заметьте, что этот алгоритм не лучше и не хуже, чем без сета, который работает за \(O(V^2 + E)\). Ведь если \(E = O(V^2)\) (граф почти полный), то Дейкстра без сета работает быстрее, а если, наример, \(E = O(V)\), то Дейкстра на сете работает быстрее. Учитывайте это, когда выбираете алгоритм.