Обход в ширину

Обход в ширину - алгоритм, использующийся для поиска кратчайшего пути от одной вершины до другой в невзвешенном графе.

Пусть нам дан граф и надо найти кратчайший путь от $s$ до $t$ или сказать, что такого пути нет.

Запустим “волну” из $s$, которая будет каждую итерацию распространяться на все вершины, соседние с уже задетыми “волной”, но ещё не посещённые. Нетрудно заметить, что расстояние между $s$ и $t$ в такой модели - номер итерации, на которой была использована вершина $t$. Если $t$ не была использована, то расстояние - $+\infty$.

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

Реализация

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

Кроме того, будем поддерживать расстояние до каждой вершины: $d[s] = 0$, а когда мы кладём новую вершину $u$ через её соседа $v$, объявим $d[u] = d[v] + 1$. Изначально массив $d$ будет заполнен $+\infty$. Он же будет служить массивом $used$: у посещённых вершин значение $d$ будет меньше бесконечности, а у непосещённых - $+\infty$.

int n;
vector<int> d(n, INF), p(n, -1);
vector<vector<int>> g(n);

vector<int> bfs(int s, int t) {
    d[s] = 0;
    queue<int> q{s};
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        
        for (int u : g[v]) {
            if (d[v] + 1 < d[u]) {
                d[u] = d[v] + 1;
                p[u] = v;
                q.push(u);
            }
        }
    }
    
    vector<int> res{t};
    while (p[res.back()] != -1) {
        res.push_back(p[res.back()]);
    }
    reverse(res.begin(), res.end());
    return res;
}

Асимптотика

Нетрудно заметить, что каждую вершину посетили один раз и при этом перебрали все рёбра, исходящие из неё.

Тогда асимптотика - $O(n + m)$.

Вариации

У алгоритма существует много модификаций. Тут рассмотрим несколько из них:

0-1 BFS

В этой модификации допустимы два веса рёбер - 0 и 1.

Для решения задачи создадим две очереди вместо одной - в первую будем класть вершины, по которым мы дошли через 0-ребро, а во вторую - те, до которых мы дошли через 1-ребро.

Теперь каждый раз, прежде чем рассмотреть новую вершину из 1-очереди, будем рассматривать все вершины из 0-очереди, пока она не станет пустой.

Это работает, потому что до всех вершин, достижимых друг из друга по нулям (то есть у всех вершин, лежащих в одной компоненте связности при удалении всех 1-рёбер) одинаковое расстояние, ведь если мы пришли в одну, мы можем прийти в любую другую по нулям и расстояние не увеличится.

Таким образом мы берём обычный BFS, но перед рассмотрением каждой вершины рассматриваем всё, достижимое по нулям.

Пути в таблице

Часто встречаются задачи, когда граф представлен таблицей, где какие-то клетки можно посещать, а другие - нельзя (пусть это хранится в массиве $a$ - от available).

Такие таблицы можно приводить к графам и решать задачу о поиске пути обычнымм методом, но как правило удобнее работать с таким графом как с таблицей.

Поскольку мы не храним рёбра явно, нам нужно уметь получать их по $(x,y)$ текущей клетки.

Для этого удобно использовать массив сдвигов $dx$, $dy$: мы запоминаем, каким образом могут измениться координаты клетки за один ход, записываем в заранее созданный массив и вместо обычного цикла по смежным вершинам перебираем сдвиги.

Затем считаем новые координаты и проверим, валидна ли полученная клетка, то есть не вышли ли мы за границы массива, и доступна ли она. Данные проверки полезно выносить в отдельную функцию $check(x, y)$.

Например, так это будет выглядеть, когда из клетки можно ходить в соседей по горизонтали или вертикали:

bool check(x, y) {
    return 0 <= x && x < n && 0 <= y && y < m && a[x][y] == 1;
}

vector<pair<int, int>> d{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

while (!q.empty()) {
    ...
    for (auto [dx, dy] : d) {
        int x1 = x + dx, y1 = y + dy;
        if (check(x1, y1)) {
            ...
        }
    }
}

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

Данный алгоритм умеет на взвешенном (но без отрицательных рёбер) графе с заданной вершиной $s$ найти длину кратчайшего пути от $s$ до всех других вершин в графе. Небольшая модификация в виде сохранения предков позволяет дополнительно восстановить путь до любой вершины.

Сам алгоритм работает следующим образом: в ходе исполнения поддерживается массив чисел $d[v]$, хранящий кратчайшее расстояние до всех вершин. Изначально полагается $d[s] = 0, \ \forall v \neq s: \ d[v] = +\infty$.

После этого производится $n$ итераций, на каждой из которых выбирается ещё не выбранная вершина $v$ с минимальным значением $d[v]$. После того, как такая вершина найдена, она отмечается выбранной и через неё производится релаксация: для всех вершин $u$, соединённых с ней, устанавливается $d[u] = min(d[u], d[v] + w_{vu})$.

Доказательство корректности

Докажем по индукции, что в момент посещения вершины $v$ $d[v]$ действительно будет длиной кратчайшего пути от $s$ до $v$ - будем обозначать эту величину $\rho(s, v)$.

База очевидна: первой будет посещена вершина $s$ и поскольку отрицательных рёбер, а значит, и отрицательных циклов, нет, $\rho(s, s) = d[s] = 0$.

Пусть утверждение выполнено для какого-то набора вершин и следующей вершиной алгоритм посещает $v$.

Для начала заметим, что $\rho(s, v) \leq d[v]$, потому что алгоритм никак не мог найти путь короче минимального.

Теперь рассмотрим кратчайший путь от $s$ до $v$.

Какая-то часть вершин на этом пути уже посещена, а какая-то - ещё нет. Возьмём первую непосещённую вершину - обозначим её за $u$. Кроме того, возьмём предшествующую ей вершину на этом пути (она уже посещена), и обозначим её за $q$.

Понятно, что $\rho(s, u) = d[q] + w_{qu}$: по предположению индукции первое слагаемое - длина кратчайшего пути до $q$, а из выбора пути до $v$ следует, что кратчайший путь до $u$ проходит через $q$ и ребро $w_{qu}$.

$q$ уже посещена, значит, в момент её посещения было установлено $d[u] = d[q] + w_{qu}$.

С другой стороны, алгоритм выбрал вершину $v$, а не $u$, а значит, $d[v] \leq d[u]$.

Наконец, из неотрицательности рёбер следует $\rho(s, u) \leq \rho(s, v)$

Получаем систему неравенств $d[v] \leq d[u] = \rho(s, u) \leq \rho(s, v)$, а значит, $\rho(s, v) \leq d[v] \leq \rho(s, v)$, то есть $d[v] = \rho(s, v)$, что и требовалось.

Реализация

def dijkstra(s):
    valid = [True] * n
    weight = [float('inf')] * n
    weight[s] = 0
    for _ in range(n):
        min_weight = float('inf')
        id_min_weight = -1
        for i in range(len(weight)):
            if valid[i] and weight[i] < min_weight:
                min_weight = weight[i]
                id_min_weight = i
        for i in range(n):
            if weight[id_min_weight] + matrix[id_min_weight][i] < weight[i]:
                weight[i] = weight[id_min_weight] + matrix[id_min_weight][i]
        valid[id_min_weight] = False
    return weight[finish]

Асимптотика

Мы выполняем $n$ итераций, каждая итерация занимает $O(n)$ действий на поиск минимальной вершины, и дополнительно все итерации суммарно делают $O(m)$ действий во время релаксации. Получаем асимптотику $O(n^2 + m)$, и это оптимальная асимптотика для плотных графов, в которых $m \approx n^2$.

Однако для разреженных графов можно добиться лучшей асимптотики.

Дейкстра с логарифмом для разреженных графов

Значительную часть сложности составляет поиск вершины с наименьшим $d[v]$. Оптимизацией именно этого поиска мы и займёмся.

Для этого вспомним о $bfs$: по сути этот алгоритм - частный случай Дейкстры, когда все веса единичные.

В том алгоритме мы поддерживали вершину с минимальным $d[v]$ с помощью очереди и пользовались тем, что она оказывалась отсортирована по построению.

Для оптимизации Дейкстры мы возьмём какую-нибудь структуру, поддерживающую минимум - например, set или priority_queue в языке C++. Изначально в структуре будет лежать пара $(0, s)$.

Такой вариант также позволяет избавиться от массива посещённых вершин.

Set

Каждый раз, когда мы обновляем значение в вершине, будем добавлять её вместе с её $d[v]$ в set в виде пары $(d[v], v)$ и удалять её старое значение, если таковое там есть.

При извлечении вершины необходимо извлечь первую вершину из сета.

Итоговая асимптотика - $O(n\log n + m\log n) = O(m\log n)$.

struct edge {
    int to, v;

    edge(int to_, int v_) : to(to_), v(v_) {};
};

vector<int> d(n, INF);
vector<vector<edge>> g(n);

set<pair<int, int>> q;

d[s] = 0;
q.insert({d[s], s});

while(!q.empty()) {
    auto[dist, v] = *q.begin();
    q.erase(q.begin());
    
    if (dist > d[v]) {
        continue;
    }
    
    for (auto &[u, w]: g[v]) {
        if (d[v] + w < d[u]) {
            d[u] = d[v] + w;
            q.insert({d[u], u});
        }
    }
}

Priority queue

Очередь работает немного лучше сета, потому что у неё меньше внутренняя константа. Тем не менее, у неё есть серьёзный недостаток - из неё нельзя удалять элементы. Для обхода этого недостатка сделаем небольшой трюк - сразу после извлечения вершины сравним расстояние, с которым она лежала в очереди, с уже подсчитанным до неё расстоянием. Если в очереди лежало неоптимальное расстояние - пропустим вершину.

Кроме того, важно помнить, что упорядоченность элементов в очереди по умолчанию не такая, как нам надо - можно написать свой компаратор, чтобы упорядоченность была правильной, а можно просто класть вершины с расстояниями, домноженными на $-1$ - это как раз изменит упорядоченность на правильную.

У такого решения будет асимптотика $O(m\log m)$, что хуже, чем $O(m\log n)$ для сета, но из-за того, что $\log m \leq \log n^2 \leq 2\log n$ и из-за заметной разницы в скорости работы сета и очереди с приоритетами - на практике данное решение заметно быстрее решения с сетами.