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

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

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

3 node, нэг чиглэлтэй edge-үүд: 1 → 2 (5), 2 → 3 (1), 1 → 3 (9). 1-ээс 3 хүртэл, 3-аас 1 хүртэлх хамгийн богино зайг ол.

1 → 3 шууд 9, харин 2-р node-оор дамжвал 5 + 1 = 6. 3-аас 1 рүү очих edge огт байхгүй. Хариу: 6 ба -1.

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

Нэг хос асуух бүрт Dijkstra ажиллуулж болно. Гэтэл асуулт олон бол бүх хосыг урьдчилан бодсон нь дээр.

Гол санаа: дамжиж болох node-уудыг нэг нэгээр нэмнэ. Эхэндээ ямар ч node-оор дамжихгүй, зөвхөн шууд edge. Дараа нь k-р node-оор дамжихыг зөвшөөрөөд хос бүрт d[i][k] + d[k][j] нийлбэрийг d[i][j]-тэй харьцуулна. k = n болоход бүх зам тооцогдсон байна.

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

d[i][j]
i-р node-оос j-р node хүртэлх одоогоор олдсон хамгийн богино зай.
k
Дамжих node. Хамгийн гадна loop.
INF
1e9. Зам олдоогүйг илэрхийлнэ. INF + INF = 2 · 10⁹ нь int-д багтах тул нэмэхэд overflow болохгүй.
adjacency matrix
Graph-ыг n × n хүснэгтээр хадгалах арга. Энд d нь өөрөө тийм хүснэгт.
i \ j12341
0
4
7
∞
2
∞
0
1
∞
3
∞
∞
0
2
4
∞
3
∞
0

d[i][j] нь i-р node-оос j-р node хүртэлх зай. Эхэндээ зөвхөн шууд edge-үүд л мэдэгдэнэ, бусад нь ∞.

Алхам 1 / 13
Хурд
  • Дамжих node k: мөр ба багана
  • Нэмж буй хоёр зай
  • Богиносгосон зай
  • Асуултын хариу
Слайд 1 / 7

Бүх хосын зай

Dijkstra нэг node-оос л зай олдог. Floyd–Warshall бүх хос node-ын зайг нэг дор олно. Хүснэгтийн i мөр, j багана нь i-р node-оос j-р node хүртэлх зай.

floyd-warshall.cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, m, q, d[405][405];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) d[i][j] = INF;
d[i][i] = 0;
}
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
d[u][v] = w;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (d[i][k] + d[k][j] < d[i][j]) {
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
cin >> q;
for (int t = 0; t < q; t++) {
int u, v;
cin >> u >> v;
cout << (d[u][v] == INF ? -1 : d[u][v]) << '\n';
}
return 0;
}

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

"u → v хэд вэ?" гэсэн олон асуултад шууд хариулахын тулд бүх хос node-ын зайг урьдчилан бодно. Node цөөн (n ≤ 400 орчим) үед хамгийн энгийн арга.

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

1. d[i][i] = 0, edge бүрт d[u][v] = w, бусад нь ∞. 2. Дамжих node k = 1, 2, …, n бүрийн хувьд бүх (i, j) хосыг шалгана. 3. d[i][k] + d[k][j] < d[i][j] байвал d[i][j] = d[i][k] + d[k][j]. 4. k нь хамгийн гадна loop байх ёстой. k бүрийн дараа эхний k node-оор дамжих бүх зам бодогдсон байна. 5. Асуулт бүрт d[u][v]-г хэвлэнэ. ∞ бол зам байхгүй тул -1. Оролт: эхний мөрөнд n m, m мөрөнд «u v w» (нэг чиглэлтэй edge u → v), дараа нь асуултын тоо q ба q мөрөнд «u v».

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

k-р алхмын дараа d[i][j] нь зөвхөн 1…k node-уудаар дамжих хамгийн богино зам байна. Шинэ k-г зөвшөөрөхөд хамгийн богино зам k-гээр огт дамжихгүй (хуучин утга) эсвэл яг нэг удаа дамжина (d[i][k] + d[k][j]). Сөрөг cycle байхгүй бол k-гээр хоёр удаа дамжих нь ашиггүй.

Гурван давхар loop: хугацаа O(n³), санах ой O(n²). n = 400 бол 64 сая алхам, нэг секунд хүрэхгүй. n = 2000 бол 8 тэрбум, хэтэрхий удаан.

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

  • k-г дотор loop болгох. Тэгвэл d[i][k] бэлэн болоогүй байхад ашиглагдаж, хариу буруу гарна. k үргэлж хамгийн гадна.
  • d[i][i] = 0 тавихаа мартах.
  • INF-ийг INT_MAX гэж авах. INT_MAX + 1 overflow болж сөрөг тоо гарна.
  • Ижил хоёр node-ын хооронд олон edge байвал сүүлийнхийг нь л хадгалах. d[u][v] = min(d[u][v], w) гэж бич.

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

  • Хүрэх замгүй хос: INF хэвээр, -1 хэвлэнэ.
  • u = v асуулт: хариу 0.
  • Сөрөг cycle байвал зарим d[i][i] сөрөг болно.

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

  1. Анимацийн жишээнд 1 → 4 хамгийн богино зай хэд вэ?

    Хариу харах

    7: 1 → 2 → 3 → 4, урт 4 + 1 + 2.

  2. n = 100 бол дотор loop нийт хэдэн удаа ажиллах вэ?

    Хариу харах

    100³ = 1 000 000.

  3. Яагаад INF-ийг 1e9 гэж авдаг вэ?

    Хариу харах

    Хоёр INF нэмэхэд 2 · 10⁹ гарна. Энэ нь int-ийн дээд хязгаар 2 147 483 647-гоос бага тул overflow болохгүй.

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

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

  1. 1.Тойрог graph: 1 → 2, 2 → 3, 3 → 4, 4 → 1 (бүгд урт 2), 1 → 3 (5). 1 → 4 ба 4 → 3-ын хариуг ол.

    Hint харах

    Тойргоор явах уу, 1 → 3 edge-ийг ашиглах уу, хоёуланг нь харьцуул.

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

    1 → 4: 1 → 2 → 3 → 4 = 6. 4 → 3: 4 → 1 → 2 → 3 = 6. Хоёулаа 6.

  2. 2.Graph-д сөрөг cycle байгаа эсэхийг шалгадаг болго.

    Hint харах

    Node өөрөөсөө өөр рүүгээ буцах зам сөрөг байж болох уу?

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

    Гурван loop дууссаны дараа d[i][i] < 0 байх i олдвол сөрөг cycle бий.

  3. 3.Зай биш, i-ээс j рүү зам байгаа эсэхийг л мэдэх хэрэгтэй бол кодыг хялбарчил.

    Hint харах

    Нэмэх, min авахын оронд логик үйлдэл хэрэглэ.

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

    reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]). Үүнийг transitive closure гэдэг.

Жишээ

Оролт

4 5
1 2 4
1 3 7
2 3 1
3 4 2
4 2 3
3
1 4
3 2
4 1

Гаралт

7
5
-1

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

Бодлого

Хичээл

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