Нэг node-оос бусад бүх node хүртэлх хамгийн богино замыг олно. Үргэлж хамгийн ойр node-ыг түрүүлж авдаг.

Advanced & LegendХугацаа: O((n + m) log m)Санах ой: O(n + m)
HackerRank дээр бодох

Эхлээд жижиг бодлого

4 node-той чиглэлгүй graph байна. Edge-үүд: 1–2 (урт 1), 2–3 (урт 2), 1–3 (урт 5), 3–4 (урт 1). 1-р node-оос бусад бүх node хүртэлх хамгийн богино зайг олъё.

1 → 3 шууд явбал 5, харин 1 → 2 → 3 гэвэл 1 + 2 = 3. Хариу: 0 1 3 4.

Энгийн аргаас санаа руу

Энгийн арга бол бүх замыг туршиж үзэх. Замын тоо node-ын тоогоор экспоненциал өснө. BFS ч энд туслахгүй, учир нь edge-үүдийн урт өөр өөр.

Гол санаа: эхлэлээс хамгийн ойр, хараахан эцэслэгдээгүй node-ыг авъя. Бүх жин эерэг тул түүнд өөр замаар үүнээс ойр хүрэх боломжгүй. Тэр node-оос хөршүүдийн зайг сайжруулна. Хамгийн ойрыг хурдан олохын тулд priority queue хэрэглэнэ.

Нэр томьёо ба тэмдэглэгээ

d[v]
Эхлэлээс v node хүртэл одоогоор олдсон хамгийн богино зай. Эхэндээ INF.
pq
(зай, node) хосуудын priority queue. greater<> тул хамгийн бага зайтай хос түрүүлж гарна.
relax
d[u] + w < d[v] бол d[v]-г багасгах алхам.
хуучин бичлэг
pq-д үлдсэн, зай нь аль хэдийн сайжирсан хос. du > d[u] бол алгасна.
g[u]
u node-ын хөршүүдийн жагсаалт (adjacency list): {v, w} хосууд.
421562361d=∞2d=∞3d=∞4d=∞5d=∞6d=∞
pq: (зай, node)
хоосон

Эхлэл бол 1-р node. Бусад node бүр хүртэлх хамгийн богино замыг олъё. Edge дээрх тоо бол замын урт.

Алхам 1 / 32
Хурд
  • Одоогийн node ба edge
  • Зай нь сая багассан
  • pq-д хүлээж буй
  • Зай нь эцэслэгдсэн, замын edge
  • Хүрэх замгүй
Слайд 1 / 7

Хамгийн богино зам

Хотуудыг замаар холбосон газрын зураг гэж төсөөл. Node бол хот, edge бол зам, edge дээрх тоо бол замын урт. Эхлэх хотоос бусад бүх хот хүртэлх хамгийн богино замыг олъё.

dijkstra.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int n, m, s;
vector<pair<int, int>> g[100005];
ll d[100005];
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
cin >> s;
for (int i = 1; i <= n; i++) d[i] = INF;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
d[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [du, u] = pq.top();
pq.pop();
if (du > d[u]) continue;
for (auto [v, w] : g[u]) {
if (d[u] + w < d[v]) {
d[v] = d[u] + w;
pq.push({d[v], v});
}
}
}
for (int i = 1; i <= n; i++) cout << (d[i] == INF ? -1 : d[i]) << ' ';
return 0;
}

Юунд хэрэгтэй вэ?

Сөрөг жингүй graph-д хамгийн богино замыг хурдан олно. Газрын зургийн апп ч ийм санаа ашигладаг. Олимпиадын graph бодлогод хамгийн их хэрэглэгддэг алгоритмын нэг.

Яаж ажилладаг вэ?

1. Эхлэх node-ын зай d[s] = 0, бусад нь ∞. (0, s) хосыг priority queue буюу pq-д хийнэ. 2. pq-д байгаа хамгийн бага зайтай (du, u) хосыг гаргана. 3. du > d[u] бол энэ хуучин бичлэг тул алгасна. 4. u node-ын хөрш v бүрт d[u] + w < d[v] байвал d[v] = d[u] + w болгоод (d[v], v) хосыг pq-д нэмнэ. 5. pq хоосортол давтана. Хүрэх замгүй node-ын зай ∞ хэвээр үлдэх тул -1 гэж хэвлэнэ. Оролт: эхний мөрөнд n m, дараагийн m мөрөнд «u v w» (чиглэлгүй edge, node-ууд 1…n), сүүлд нь эхлэх node s.

Яагаад зөв, хэр хурдан бэ?

pq u node-ыг гаргаж өгөхөд d[u] эцсийнх болно. Учир нь өөр ямар ч зам pq-д хүлээж буй, d[u]-гаас багагүй зайтай ямар нэг node-оор дамжих ёстой. Жин сөрөг биш тул түүнээс цааш явахад зай багасахгүй.

Edge бүр хамгийн ихдээ нэг удаа pq-д хос нэмнэ. pq дээрх үйлдэл бүр O(log m). Нийт хугацаа O((n + m) log m). n = m = 200 000 бол 7 сая орчим үйлдэл, хурдан.

Түгээмэл алдаа

  • Сөрөг жинтэй edge-тэй graph-д ашиглах. Гарсан node-ын зай эцсийнх гэдэг баталгаа алдагдана. Bellman–Ford хэрэглэ.
  • if (du > d[u]) continue; мөрийг мартах. Хариу зөв хэвээр ч хуучин бичлэг бүрээс хөршүүдийг дахин шалгаж, удааширна.
  • Зайг int-ээр хадгалах. n = 10⁵, жин 10⁹ бол зам 10¹⁴ хүрнэ. long long ба INF = 1e18 хэрэгтэй.
  • Чиглэлгүй graph-д edge-ийг ганц тал руу нь нэмэх. g[u] ба g[v] хоёуланд нэмнэ.
  • priority_queue-г greater<>-гүй бичих. Анхдагч нь хамгийн ихийг гаргадаг.

Хязгаарын тохиолдол

  • Хүрэх замгүй node: d нь INF хэвээр, -1 хэвлэнэ.
  • Бүх жин 1: хариу нь BFS-ийн хариутай ижил.
  • Эхлэх node-ын зай үргэлж 0.

Өөрийгөө шалга

  1. Дээрх жижиг жишээнд эхлэл нь 4-р node бол хариу юу вэ?

    Хариу харах

    4 3 1 0.

  2. 3 node, ганц 1–2 (урт 5) edge, эхлэл 1. Хариу юу вэ?

    Хариу харах

    0 5 -1. 3-р node руу зам алга.

  3. Нэг node pq-д хэд хэдэн удаа орж болох уу?

    Хариу харах

    Болно. Зай нь сайжрах бүрт шинэ хос нэмэгдэнэ. Хуучин хосууд нь хожим гараад алгасагдана.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.Анимацийн жишээ graph дээр (эхлэл 1) node-ууд ямар дарааллаар эцэслэгдэхийг бич.

    Hint харах

    Гарах үедээ du == d[u] байсан node л эцэслэгдэнэ. Зай ижил бол бага дугаартай нь түрүүлнэ.

    Хариу ба тайлбар

    1 (0), 3 (2), 2 (3), 4 (8), 5 (8), 6 (11). Хариу 0 3 2 8 8 11.

  2. 2.Хамгийн богино замын node-уудыг өөрсдийг нь хэвлэдэг болго.

    Hint харах

    d[v] сайжрах бүрт v-д хаанаас ирснийг хадгал.

    Хариу ба тайлбар

    par[v] = u гэж хадгална. Төгсгөлөөс par-аар эхлэл хүртэл буцаж явж, жагсаалтыг урвуу эргүүлж хэвлэнэ.

  3. 3.Graph чиглэлтэй (u → v) бол кодыг яаж өөрчлөх вэ?

    Hint харах

    Оролт уншдаг хэсгийг хар.

    Хариу ба тайлбар

    g[v].push_back({u, w}) мөрийг устгана. Үлдсэн код хэвээр ажиллана.

Жишээ

Оролт

6 8
1 2 4
1 3 2
2 3 1
2 4 5
3 5 6
4 5 2
4 6 3
5 6 6
1

Гаралт

0 3 2 8 8 11

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.