Рассмотрим взвешенный граф, то есть у всех его ребер есть вес - некоторое число. Можно представить, что это цена, за которую мы можем по нему проехать.
Как его хранить? Давайте просто в списке смежности вместо номеров вершин соседа хранить пару (номер соседа, вес ребра до него).
Давайте решать задачу посика кратчайшего пути в графе - мы хотим за наименьшую стоимость проехать из вершины $A$ в $B$.
Обычно будем считать, что в графе нет циклов отрицательного веса - иначе кратчайшее расстояниие может быть равно минус бесконечности.
Для данной задачи есть несколько алгоритмов решения.
Мы с вами уже знаем динамическое программирование, давайте рассмотри следующую динамику:
$d_{i j}^k$ - это длина кратчайшего пути от вершины $i$ до $j$, используя как промежуточные только вершины из первых $k$ = $d_{i j}^k$ (напоминает рюкзак).
База динамики ($k = 0$) определяется только путями из одного ребра. Если есть ребро из $i$ в $j$ стоимостью $c$, то $d_{i j}^{0}$ = $c$. Если таких ребер несколько, то, конечно, надо взять минимум.
Если мы хотим посчитать $d_{i j}^{k}$, то у нас есть два варианта
1) Не брать на пути нигде $k$-ую вершину, тогда $d_{i j}^{k}$ = $d_{i j}^{k - 1}$
2) Взять где-нибудь в пути k-ую вершину, тогда путь разбивается на две части - от $i$ до $k$ и от $k$ до $j$, раз итоговый путь кратчайший, то и и эти два пути должны быть кратчайшми, а значит формула $d_{i j}^{k}$ = $d_{i k}^{k - 1}$ + $d_{k j}^{k - 1}$
В результате ответ - $d_{A B}^{n}$,
Можете подумать, как по такой динамике восстановить сам путь.
Также заметим, что вместо трехмерной динамики в этом алгоритме можно использовать двухмерную, храня в $dp_{ij}$ последнее известное значение из $dp_{ij}^0$, $dp_{ij}^1$ $dp_{ij}^2$, $\ldots$, $dp_{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$. Например:
Назовем релаксацией обновление ответа для вершины $b$ через ребро $(a, b, c)$ таким способом: $d[b] = \min(d[b], d[a] + c)$.
Теперь давайте каждый раз доставать вершину, для которой расстояние от А сейчас минимально, и мы еще ее не смотрели и затем обновлять всех ее соседей. Допустим вершина с минимальным расстоянием - 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]);
}
}