Кратчайшие пути в графе

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

Как его хранить? Давайте просто в списке смежности вместо номеров вершин соседа хранить пару (номер соседа, вес ребра до него).

Давайте решать задачу посика кратчайшего пути в графе - мы хотим за наименьшую стоимость проехать из вершины $A$ в $B$.

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

Для данной задачи есть несколько алгоритмов решения.

Алгоритм Флойда

Мы с вами уже знаем динамическое программирование, давайте рассмотри следующую динамику:

$d_{ij}^k$ - это длина кратчайшего пути от вершины $i$ до $j$, используя как промежуточные только вершины из первых $k$ = $d_{ij}^k$ (напоминает рюкзак).

База динамики ($k=0$) определяется только путями из одного ребра. Если есть ребро из $i$ в $j$ стоимостью $c$, то $d_{ij}^0$ = $c$. Если таких ребер несколько, то, конечно, надо взять минимум.

Если мы хотим посчитать $d_{ij}^k$, то у нас есть два варианта

1. Не брать на пути нигде $k$-ую вершину, тогда $d_{ij}^k$ = $d_{ij}^{k-1}$

2. Взять где-нибудь в пути k-ую вершину, тогда путь разбивается на две части - от $i$ до $k$ и от $k$ до $j$, раз итоговый путь кратчайший, то и и эти два пути должны быть кратчайшми, а значит формула $d_{ij}^k$ = $d_{ik}^{k-1}$ + $d_{kj}^{k-1}$

В результате ответ - $d_{AB}^n$,

Можете подумать, как по такой динамике восстановить сам путь.

Также заметим, что вместо трехмерной динамики в этом алгоритме можно использовать двухмерную, храня в $d{p}_{ij}$ последнее известное значение из $d{p}_{ij}^0$, $d{p}_{ij}^1$ $d{p}_{ij}^2$, $\dots$, $d{p}_{ij}^n$.

for(int k = 0; k < n; k++){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
        }
    }
}

Теоретическое задание

Подумайте, как находить циклы отрицательного веса с помощью Флойда.

Плюсы алгоритма в том, что он находит расстояние сразу от всех вершин графа до остальных, а минус - алгоритм работает за $O(N^3)$;

Практическое задание

Первые две задачи на алгоритм Флойда.

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

Для этого алгоритма придется рассматривать только графы без отрицательных рёбер.

Алгоритм Дейкстры решает немного другую задачу: он находит расстояние от одной вершины $A$ до каждой вершины. Давайте для каждой вершины хранить расстояние до нее из вершины $A$ в массиве $d$. Например: * $d[A]=0$ * $d[x]=\mathrm{\infty }$, если x не достижима из A

Назовем релаксацией обновление ответа для вершины $b$ через ребро $(a,b,c)$ таким способом: $d[b]=min(d[b],d[a]+c)$.

• При таком действии ответ не может стать лучше, чем кратчайшее расстояние до $b$, так как мы просто пользуемся путем для вершины $a$ и продлеваем его в $b$.
• Если мы прорелаксировали все ребра в кратчайшем пути в правильном порядке до вершины $b$, то мы получим кратчайший путь до $b$.

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

Давайте докажем корректность алгоритма по индукции:

База) Первой вершиной мы всегда рассмотрим $A$, но для нее верно, что расстояние от $А$ до $А$ = 0;

Шаг) Мы достали вершину $i$, нам известно, что для всех ее предков ответ - корректен, но тогда, допустим, что для $i$-ой вершины мы нашли ответ больший, чем надо, тогда это значит, что мы должны прийти из еще не рассмотренной вершины, но так как ребер отрицательного веса в графе нет, то такое невозможно $\Rightarrow$ мы доказали

https://visualgo.net/en/sssp?slide=1

Есть две возможные реализации алгоритма

1. реализация помощью нахождения минимального расстояния внутри массива за линию. Так как мы для каждого шага находим минимальную вершину, то мы сделаем не более $N$ шагов, но при этом на каждом шаге мы находим минимум за линию, то есть алгоритм работает за $O(N^2)$.

for (int i = 0; i < n; ++i){
    int uk = -1;
    for (int j = 0; j < n; j++){
        if ((mark[j] == 0) && ((uk == -1) || (d[j] < d[uk]))){
                uk = j;
        }
    }
    for (int j = 0; j < n; j++){
        if ((j != uk) && (g[uk][j] != -1)) d[j] = min(d[j], g[uk][j] + d[uk]);
    }
    mark[uk] = 1;
}

2. Реализация за $O(MlognN+NlogN)$ с помощью нахождения минимального расстояния внутри кучи/сета за логарифм. Так как для каждой вершины мы сделаем не более одного извлекания из структуры + каждое ребро мы используем максимум два раза. Для этого давайте в выбранной структуре хранить пару (расстояние, вершина); Первый код реализован с set, второй с кучей. Так как в куче нет компаратора на возрастание, то надо либо сделать свой, либо домножить расстояние на -1;

while (used.size()) {
    int v = (*(used.begin())).second;
    for (int i = 0; i < g[v].size(); i++) {
        int to = g[v][i].first, c = g[v][i].second;
        if (dist[v] + c < dist[to]) {
            used.erase({dist[to], to});
            dist[to] = dist[v] + to;
            used.insert({dist[to], to});
        }
    }
    used.erase({dist[v], v});
}

while (!q.empty()) {
        int v = q.top().second;
        q.pop();
    for (int j = 0; j < g[v].size(); ++j) {
        int to = g[v][j].first, c = g[v][j].second;
        if (d[v] + c < d[to]) {
            d[to] = d[v] + c;
            q.push({-d[to], to});
        }
    }
}

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

Теоретическое задание

Приведите примеры, когда каждый из алгоритмов работает лучше.

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

Практическое задание

3-5 Задача на алгоритм Дейкстры.

Форд-Беллман

Этот алгоритм решает ту же задачу, что и Дейкстра, но зато может работать с отрицательными ребрами!

Давайте заведем массив расстояний, как и в дейкстре, для стартовой вершины расстояние = 0. Алгоритм состоит в релаксации каждого ребра в графе $N-1$ раз.

Это работает потому, что в кратчайшем пути не больше, чем $N-1$ ребро, и если мы прорелаксируем их в таком порядке, этот путь найдется. После $N-1$ прохода по всем ребрам и их релаксации мы точно это сделаем и найдем кратчайший путь.

Также в этом случае удобнее хранить список ребер явно вместо списка смежности.

int from[m], to[m], cost[m];
for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < m; ++j) {
                d[to[j]] = min(d[to[j]], d[from[j]] + cost[j]);
    }
}

Теоретическое задание

Подумайте, как найти цикл отрицательного веса с помощью этого алгоритма.

Практическое задание

Решите задачи 6 и 7.

Ссылка на контест

https://informatics.msk.ru/mod/statements/view.php?id=33380#1