Бүх edge-ийг n − 1 удаа тойрч шалгаад сөрөг жинтэй graph-д ч хамгийн богино зайг олно. Сөрөг cycle байгаа эсэхийг ч илрүүлнэ.

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

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

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

1 → 2 шууд 4. Гэтэл 1 → 3 → 2 гэвэл 5 − 2 = 3. Хариу: 0 3 5.

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

Dijkstra хамгийн ойр node-ыг эцэслэдэг. Сөрөг edge байвал "одоо хамгийн ойр" node-д хожим илүү богино зам олдож болно. Тиймээс тэр санаа ажиллахгүй.

Bellman–Ford илүү энгийн: бүх edge-ийг дахин дахин relax хийнэ. Хамгийн богино зам хамгийн ихдээ n − 1 edge-тэй. Тойрог бүр ийм замын дахиад нэг edge-ийг зөв болгодог тул n − 1 тойрог хангалттай. Дараа нь нэг удаа шалгахад зай багассаар байвал сөрөг cycle бий.

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

d[v]
Эхлэлээс v хүртэл одоогоор олдсон хамгийн богино зай. Эхэндээ INF.
тойрог
Бүх m edge-ийг нэг удаа шалгах. Гадна loop r = 1…n − 1.
relax
d[u] + w < d[v] бол d[v] = d[u] + w.
сөрөг cycle
Жингийн нийлбэр нь сөрөг cycle. Тойрох тусам зам богиносож, хамгийн богино зам гэж байхгүй болно.
-1-233621d=02d=∞3d=∞4d=∞5d=∞
edge-үүд (шалгах дарааллаар)
5→3 (-1)4→5 (-2)2→4 (3)2→3 (3)1→3 (6)1→2 (2)

Эхлэл бол 1-р node: d[1] = 0, бусад нь ∞. Edge бүр нэг чиглэлтэй, зарим нь сөрөг жинтэй. Бүх edge-ийг 4 удаа тойрч шалгана.

Алхам 1 / 12
Хурд
  • Эхлэх node
  • Ашиглаж буй edge ба node
  • Зай нь багассан
  • Зай нь мэдэгдсэн
  • Эцсийн зай
  • Хүрэх замгүй
Слайд 1 / 6

Сөрөг жинтэй зам

Зарим edge-ийн жин сөрөг: тэр замаар явбал зай багасна. Dijkstra ийм үед алдаж болно. Bellman–Ford бүх edge-ийг дахин дахин шалгаж, зөв хариуг олно.

bellman-ford.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int n, m, s, u[5005], v[5005], w[5005];
ll d[2505];
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) cin >> u[i] >> v[i] >> w[i];
cin >> s;
for (int i = 1; i <= n; i++) d[i] = INF;
d[s] = 0;
for (int r = 1; r < n; r++) {
for (int i = 0; i < m; i++) {
if (d[u[i]] != INF && d[u[i]] + w[i] < d[v[i]]) {
d[v[i]] = d[u[i]] + w[i];
}
}
}
for (int i = 0; i < m; i++) {
if (d[u[i]] != INF && d[u[i]] + w[i] < d[v[i]]) {
cout << "NEGATIVE CYCLE\n";
return 0;
}
}
for (int i = 1; i <= n; i++) cout << (d[i] == INF ? "INF" : to_string(d[i])) << ' ';
return 0;
}

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

Сөрөг жинтэй edge байхад хамгийн богино замыг олно. Dijkstra ийм үед алдаж болдог. Мөн тойрох тусам зам богиносдог сөрөг cycle байгаа эсэхийг шалгана.

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

1. d[s] = 0, бусад нь ∞. 2. n − 1 удаа тойрно. Тойрог бүрт edge бүрийг жагсаалтын дарааллаар шалгана. 3. d[u] ≠ ∞ ба d[u] + w < d[v] байвал d[v] = d[u] + w. 4. Дахин нэг удаа бүх edge-ийг шалгана. Зай багассаар байвал сөрөг cycle бий, NEGATIVE CYCLE гэж хэвлэнэ. 5. Үгүй бол зайнуудыг хэвлэнэ. Хүрэх замгүй node-д INF гэж бичнэ. Жин сөрөг байж болох тул -1 хэрэглэхгүй. Оролт: эхний мөрөнд n m, m мөрөнд «u v w» (нэг чиглэлтэй edge u → v, w сөрөг байж болно), сүүлд нь эхлэх node s.

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

Хамгийн богино зам 1 → … → v нь k edge-тэй бол k-р тойргийн дараа d[v] зөв болно. Тойрог бүрт тэр замын дараагийн edge relax хийгддэг. Сөрөг cycle байхгүй бол зам n − 1-ээс олон edge-тэй байх шаардлагагүй. Тиймээс n − 1 тойргийн дараа бүх зай эцсийнх. Түүний дараа ч зай багасвал зөвхөн сөрөг cycle-ээс л болно.

Хугацаа O(n · m). n = 2500, m = 5000 бол 12.5 сая relax, хурдан. Харин n, m = 10⁵ бол 10¹⁰, хэтэрхий удаан.

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

  • d[u] != INF шалгалтыг мартах. INF + (−3) нь INF-ээс бага тул хүрээгүй node-оос хуурамч зам гарна.
  • Хүрэх замгүй node-д -1 хэвлэх. Зай өөрөө -1 байж болох тул энэ код INF гэж бичдэг.
  • n − 1 биш n − 2 тойрог хийх. Хамгийн урт хамгийн богино зам дутуу үлдэнэ.
  • Энэ код graph дахь бүх сөрөг cycle-ийг олно гэж бодох. d[u] != INF шалгалтын улмаас эхлэлээс хүрэхгүй cycle илрэхгүй. Бүх cycle хэрэгтэй бол бүх d-г 0-ээр эхлүүл.

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

  • Хүрэх замгүй node: INF хэвээр, хариунд INF гэж бичнэ.
  • Сөрөг edge байхгүй: Dijkstra-тай ижил хариу, гэхдээ удаан.
  • n = 1: тойрог огт хийхгүй, хариу 0.

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

  1. Анимацийн жишээ graph-ын хариу юу вэ?

    Хариу харах

    0 2 2 5 3.

  2. "Сөрөг cycle" жишээнд 1 → 2 → 4 → 5 → 3 → 1 cycle-ийн жин хэд вэ?

    Хариу харах

    −1: 2 + 1 − 3 + 2 − 3.

  3. n = 5 бол хэдэн тойрог хийх вэ?

    Хариу харах

    4 тойрог, дараа нь сөрөг cycle шалгах нэг удаа.

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

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

  1. 1."Хүрэх замгүй node" жишээнд (1 → 2 (3), 2 → 3 (−1), 4 → 3 (2), 4 → 5 (1), эхлэл 1) хариуг ол.

    Hint харах

    4-р node руу орох edge байгаа юу?

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

    0 3 2 INF INF. 4 ба 5 руу 1-ээс хүрэх зам алга.

  2. 2.Тойрогт ямар ч зай өөрчлөгдөхгүй бол эрт зогсдог болго.

    Hint харах

    Тойрог бүрт өөрчлөлт гарсан эсэхийг тэмдэглэ.

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

    bool changed = false; relax хийх бүрт changed = true; Тойрог дуусахад if (!changed) break; Хариу өөрчлөгдөхгүй, ихэнх graph дээр хурдан болно.

  3. 3.Хамгийн богино зам хамгийн ихдээ K edge-тэй байх ёстой бол яаж бодох вэ?

    Hint харах

    Тойрог бүр замыг нэг edge-ээр уртасгадаг. Гэхдээ нэг тойрог дотор хоёр edge дараалан relax болж болно.

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

    K тойрог хийнэ. Тойрог бүрийн эхэнд d-г хуулж prev гэж хадгалаад, зөвхөн prev[u] + w < d[v] гэж шинэчилнэ. Тэгвэл нэг тойрогт зам яг нэг edge-ээр л уртасна.

Жишээ

Оролт

5 6
5 3 -1
4 5 -2
2 4 3
2 3 3
1 3 6
1 2 2
1

Гаралт

0 2 2 5 3