Dijkstra algoritmi haqida bilib oling
Sizga ta cho‘qqi va ta qirraga ega yo‘naltirilgan yoki yo‘naltirilmagan og‘irlikli graf berilgan. Barcha qirra og‘irliklari manfiy emas. Shuningdek, boshlang‘ich cho‘qqi berilgan.
Har bir cho‘qqi uchun dan gacha bo‘lgan eng qisqa yo‘l uzunligini topish kerak.
Biz ikkita massivdan foydalanamiz:
d[] — har bir x cho‘qqi uchun d[x] s dan x gacha hozircha ma’lum bo‘lgan eng qisqa masofani saqlaydi;used[] — cho‘qqi allaqachon belgilanganmi-yo‘qligini ko‘rsatadi.Dastlab:
d[s] = 0d[x] = infSo‘ng tagacha iteratsiya bajariladi. Har bir iteratsiyada:
d[x] qiymati eng kichik bo‘lgan belgilanmagan x cho‘qqini tanlang;x dan chiqadigan barcha qirralarni bo‘shashtiring (relax).Agar og‘irligi len bo‘lgan (x, to) qirrasi mavjud bo‘lsa, u holda bo‘shashtirish quyidagicha:
Oxirida d[] massivi s dan barcha cho‘qqilargacha bo‘lgan eng qisqa yo‘llar uzunliklarini o‘z ichiga oladi.
Agar ayrim cho‘qqilarga s dan yetib bo‘lmasa, ularning masofalari cheksizlikka teng bo‘lib qoladi. Bunday holatda, tanlangan cho‘qqining masofasi cheksiz bo‘lishi bilanoq algoritm to‘xtashi mumkin.
Oldingi implementatsiya har bir iteratsiyada minimal masofaga ega belgilanmagan cho‘qqini topish uchun vaqt sarflaydi. Bu algoritmning eng sekin qismi bo‘lib, umumiy murakkablikni ga olib keladi.
Buni yaxshilash uchun barcha belgilanmagan cho‘qqilarni quyidagilarni qo‘llab-quvvatlaydigan ma’lumotlar tuzilmasida saqlashimiz mumkin:
Buni amalga oshirishning bir usuli:
Biz to‘plamda (d[x], x) juftliklarini saqlaymiz. Shunda eng kichik element har doim begin() da bo‘ladi.
Bo‘shashtirish vaqtida masofa yaxshilanganda, eski juftlikni o‘chirib, yangisini kiritamiz.
Bu murakkablikni quyidagigacha kamaytiradi:
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;
}