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

Данный алгоритм умеет на взвешенном (но без отрицательных рёбер) графе с заданной вершиной $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$ и из-за заметной разницы в скорости работы сета и очереди с приоритетами - на практике данное решение заметно быстрее решения с сетами.