Edge-ийн жин 0 эсвэл 1 байх graph-т хамгийн богино зайг deque ашиглан O(n + m) хугацаанд олох арга.

Advanced & LegendХугацаа: O(n + m)Санах ой: O(n + m)

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

4 node, edge нь 1 2 1, 1 3 0, 3 2 0, 2 4 1. Node 1-ээс бусад хүртэлх хамгийн бага зай хэд вэ?

Node 3 хүртэл 0 жинтэй edge-ээр 0. Node 2 хүртэл шууд явбал 1, харин 1 → 3 → 2 замаар 0 + 0 = 0. Node 4 хүртэл 0 + 1 = 1. Хариу 0 0 0 1.

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

Dijkstra энэ бодлогыг шийднэ, гэхдээ priority_queue-тэй тул O(m log n). Энгийн BFS бол жингүй graph-т л зөв.

Гол санаа: жин зөвхөн 0 эсвэл 1 бол priority_queue-ийн оронд deque хангалттай. 0 жинтэй edge-ээр очсон node-ын зай одоогийнхтой тэнцүү тул deque-ийн урд хийнэ. 1 жинтэй edge-ээр очсон node-ын зай 1-ээр их тул ард хийнэ. Ингэхэд deque үргэлж зайгаараа эрэмбэтэй байна.

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

deque
Хоёр үзүүртэй queue. push_front, push_back, pop_front бүгд O(1).
d[v]
Node 1-ээс v хүртэлх одоогоор олдсон хамгийн бага зай. Эхэндээ INF.
INF
Маш их тоо (1e9). "Хараахан хүрээгүй" гэсэн утгатай.
relax
d[u] + w < d[v] бол d[v]-г багасгах алхам.
100110111d=∞2d=∞3d=∞4d=∞5d=∞6d=∞
dq (deque)
хоосон

Edge бүрийн жин 0 эсвэл 1. Node 1-ээс бусад node хүртэлх хамгийн бага зайг олъё. Deque ашиглана: 0 жинтэй edge-ээр очсон node-ыг урд нь, 1 жинтэйг ард нь хийнэ.

Алхам 1 / 35
Хурд
  • Одоогийн node / edge
  • Зай нь сая багассан
  • Deque-д байгаа
  • Гарсан node / path-ын edge
  • Хүрэх path байхгүй
Слайд 1 / 6

Үнэгүй ба төлбөртэй зам

Зарим зам үнэгүй (жин 0), зарим нь 1 төгрөг (жин 1). Node 1-ээс бусад node хүртэл хамгийн багадаа хэдэн төгрөг төлөх вэ?

zero-one-bfs.cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n, m, d[100005];
vector<pair<int, int>> g[100005];
deque<int> dq;
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});
}
for (int i = 1; i <= n; i++) d[i] = INF;
d[1] = 0;
dq.push_back(1);
while (!dq.empty()) {
int u = dq.front();
dq.pop_front();
for (auto [v, w] : g[u]) {
if (d[u] + w < d[v]) {
d[v] = d[u] + w;
if (w == 0) {
dq.push_front(v);
} else {
dq.push_back(v);
}
}
}
}
for (int i = 1; i <= n; i++) cout << (d[i] == INF ? -1 : d[i]) << ' ';
cout << '\n';
return 0;
}

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

Зарим алхам үнэгүй, зарим нь 1 үнэтэй бодлогод хэрэглэнэ. Жишээ нь хүснэгт дээр хамгийн цөөн хана нураах. Dijkstra-аас хурдан, бичихэд амархан.

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

1. d[1] = 0, бусад нь INF. Node 1 deque-д орно. 2. Deque-ийн урдаас node u гаргана. 3. Хөрш бүрт d[u] + w < d[v] бол d[v] = d[u] + w болгоно. 4. w = 0 бол v-г deque-ийн урд, w = 1 бол ард нь нэмнэ. 5. Deque доторх зай үргэлж багаас их рүү эрэмбэтэй тул Dijkstra шиг зөв хариу гарна. 6. Хүрч чадаагүй node-д -1 хэвлэнэ. Оролт: n m, дараа нь m мөрөнд «u v w» (чиглэлгүй edge, w нь 0 эсвэл 1).

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

Deque доторх node-уудын зай хамгийн ихдээ хоёр өөр утгатай: k ба k + 1. Урд нь k-тай node-ууд, ард нь k + 1-тэй node-ууд байна. 0 жинтэйг урд, 1 жинтэйг ард хийх нь энэ дарааллыг эвддэггүй. Тиймээс deque-ийн урдаас гарах node үргэлж хамгийн бага зайтай, яг Dijkstra-гийн priority_queue шиг.

Node нэгээс олон удаа deque-д орж болох ч зай нь багасах бүрт л орно. Хугацаа O(n + m). n = 1 000 000 хүснэгтийн бодлогод ч хурдан.

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

  • 0 жинтэй edge-ийг ч deque-ийн ард хийх. Тэгвэл дараалал эвдэрч, буруу зай гарна.
  • Хүрээгүй node-д INF-ийг шууд хэвлэх. Бодлого ихэвчлэн -1 хүсдэг.
  • d[u] + w < d[v] шалгалтгүйгээр нэмэх. Тэгвэл node-ууд дахин дахин орж, хугацаа хэт удаан болно.

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

  • Бүх жин 0: node 1-тэй холбоотой бүх node-ын зай 0.
  • Бүх жин 1: энгийн BFS-тэй ижил хариу гарна.
  • Node 1-ээс хүрэхгүй node: d нь INF хэвээр тул -1 хэвлэнэ.

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

  1. 5 node, edge нь 1 2 1, 2 3 1, 4 5 0. Код юу хэвлэх вэ?

    Хариу харах

    0 1 2 -1 -1. Node 4, 5 нь node 1-тэй холбоогүй.

  2. Яагаад 0 жинтэй edge-ээр очсон node-ыг урд нь хийдэг вэ?

    Хариу харах

    Түүний зай одоогийн node-ынхтой тэнцүү буюу deque доторх хамгийн бага утга. Тиймээс түүнийг хамгийн түрүүнд гаргах ёстой.

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

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

  1. 1.Animation-ы жишээн дээр (1 2 1, 1 3 0, 2 3 0, 2 4 1, 3 5 1, 4 5 0, 4 6 1, 5 6 1) node 4-ийн зай яагаад 1 вэ?

    Hint харах

    Node 2 хүртэл 0 зайтай хүрэх замыг эхлээд ол.

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

    1 → 3 → 2 замаар node 2 хүртэл 0. Дараа нь 2 4 1 edge-ээр node 4 хүртэл 1. Мөн 3 → 5 → 4 замаар 1 + 0 = 1, ижил хариу.

  2. 2.n × m хүснэгтэд . бол хоосон, # бол хана. Зүүн дээд нүднээс баруун доод нүд хүрэхийн тулд хамгийн цөөндөө хэдэн хана нураах вэ?

    Hint харах

    Нүд бүр node. Хөрш нүд рүү шилжих edge-ийн жин нь тэр нүд хана бол 1, үгүй бол 0.

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

    Нүдний хос (r, c)-г deque-д хийнэ. Хөрш нүд # бол w = 1, . бол w = 0 гээд яг энэ кодоор явна. Баруун доод нүдний d хариу.

  3. 3.Хэд хэдэн эхлэл node-той болго: k node-оос хамгийн ойрынх нь хүртэлх зайг ол.

    Hint харах

    Энгийн BFS-д олон эхлэлийг яаж оруулдаг билээ?

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

    Эхлэл бүрийг d = 0 гээд deque-д хийнэ. Үлдсэн код өөрчлөгдөхгүй.

Жишээ

Оролт

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

Гаралт

0 0 0 1 1 2