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

Задача

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

BFS

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

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

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

Создадим массив $dist$ расстояний. Изначально $dist[s] = 0$ (поскольку расстояний от вершины до самой себя равно $0$) и $dist[v] = \infty$ для $v \neq s$.
Создадим очередь $q$. Изначально в $q$ добавим вершину $s$.
Пока очередь $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) \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$.

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

База очевидна.
Переход. Сначала докажем первую часть. Предположим, что $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 с восстановлением пути

// теперь 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$ до каждой из вершин графа. Длина пути — сумма длин рёбер в нём.

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

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

Создать массив $dist$ расстояний. Изначально $dist[s] = 0$ и $dist[v] = \infty$ для $v \neq s$.
Создать булёв массив $used$, $used[v] = 0$ для всех вершин $v$ — в нём мы будем отмечать, совершалась ли релаксация из вершины.
Пока существует вершина $v$ такая, что $used[v] = 0$ и $dist[v] \neq \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, который его дублирует, но хранит элементы по порядку. Тогда, чтобы заменить значение $(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)$, то Дейкстра на сете работает быстрее. Учитывайте это, когда выбираете алгоритм.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

bfs.md

bfs.md

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

Задача

BFS

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

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

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

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

Время работы

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

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

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

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

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

Задача

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

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

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

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

Files

bfs.md

Latest commit

History

bfs.md

File metadata and controls

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

Задача

BFS

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

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

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

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

Время работы

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

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

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

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

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

Задача

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

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

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

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