Рассмотрим взвешенный граф, то есть у всех его ребер есть вес - некоторое число. Можно представить, что это цена, за которую мы можем по нему проехать.
Как его хранить? Давайте просто в списке смежности вместо номеров вершин соседа хранить пару (номер соседа, вес ребра до него).
Давайте решать задачу посика кратчайшего пути в графе - мы хотим за наименьшую стоимость проехать из вершины \(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}\), то у нас есть два варианта
Не брать на пути нигде \(k\)-ую вершину, тогда \(d_{i j}^{k}\) = \(d_{i j}^{k - 1}\)
Взять где-нибудь в пути 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\). Например: * \(d[A] = 0\) * \(d[x] = \infty\), если x не достижима из A
Назовем релаксацией обновление ответа для вершины \(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
Есть две возможные реализации алгоритма
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;
}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