Изучите алгоритм Дейкстры
Вам дан ориентированный или неориентированный взвешенный граф с вершинами и рёбрами. Все веса рёбер неотрицательные. Также вам дана стартовая вершина .
Для каждой вершины нужно найти длину кратчайшего пути от до .
Мы используем два массива:
d[] — для каждой вершины x значение d[x] хранит текущую известную кратчайшую дистанцию от s до x;used[] — показывает, была ли вершина уже помечена.Изначально:
d[s] = 0d[x] = infЗатем мы выполняем до итераций. В каждой итерации:
x с наименьшим значением d[x];x.Если есть ребро (x, to) веса len, то релаксация означает:
В конце массив d[] содержит длины кратчайших путей от s до всех вершин.
Если некоторые вершины недостижимы из s, их расстояния остаются равными бесконечности. В этом случае алгоритм может остановиться, как только выбранная вершина имеет бесконечное расстояние.
Предыдущая реализация тратит времени в каждой итерации, чтобы найти непомеченную вершину с минимальным расстоянием. Это самая медленная часть алгоритма и приводит к общей сложности .
Мы можем улучшить это, храня все непомеченные вершины в структуре данных, которая поддерживает:
Один из способов сделать это — с помощью:
Мы храним пары (d[x], x) в множестве. Тогда наименьший элемент всегда находится в begin().
Когда расстояние улучшается во время релаксации, мы удаляем старую пару и вставляем новую.
Это уменьшает сложность до:
const int inf = 1e9;
vector<int> dijkstra(int n, int s, vector<vector<pair<int, int>>>& v) {
vector<int> d(n, inf);
vector<bool> used(n, false);
d[s] = 0;
for (int i = 0; i < n; i++) {
int x = -1;
// 1. find the unmarked vertex with minimum distance
for (int j = 0; j < n; j++) {
if (!used[j] && (x == -1 || d[j] < d[x])) {
x = j;
}
}
if (x == -1 || d[x] == inf) {
break;
}
// 2. mark the current vertex
used[x] = true;
// 3. relaxations
for (auto edge : v[x]) {
int to = edge.first;
int len = edge.second;
d[to] = min(d[to], d[x] + len);
}
}
return d;
}
set<pair<int, int>>
const int inf = 1e9;
vector<int> dijkstra(int n, int s, vector<vector<pair<int, int>>>& v) {
vector<int> d(n, inf);
d[s] = 0;
set<pair<int, int>> S;
for (int i = 0; i < n; i++) {
S.insert({d[i], i});
}
while (!S.empty()) {
// 1. get the unmarked vertex with minimum distance
int x = S.begin()->second;
int dist = S.begin()->first;
S.erase(S.begin());
if (dist == inf) {
break;
}
// 2. relaxations
for (auto edge : v[x]) {
int to = edge.first;
int len = edge.second;
if (d[x] + len < d[to]) {
S.erase({d[to], to}); // remove old value
d[to] = d[x] + len;
S.insert({d[to], to}); // insert updated value
}
}
}
return d;
}