Дар бораи алгоритми Дейкстра омӯзед
Ба шумо графи вазндори самтдор ё бесамт бо қулла ва канор дода шудааст. Ҳамаи вазнҳои канорҳо ғайриманфӣ мебошанд. Инчунин ба шумо қуллаи оғоз дода шудааст.
Барои ҳар як қуллаи , бояд дарозии кӯтоҳтарин роҳ аз то -ро ёбем.
Мо ду массивро истифода мебарем:
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)-ро дар set нигоҳ медорем. Пас элементи хурдтарин ҳамеша дар 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;
}