Граф дахь сөрөг циклийг олох¶
Бидэнд $N$ орой, $M$ ирмэгтэй чиглэлтэй жинтэй граф $G$ өгөгдсөн. Хэрэв сөрөг жинтэй цикл оршин байвал түүн дэх ийм дурын нэг циклийг ол.
Бодлогын өөр нэг томьёололд хооронд нь дурын бага жинтэй зам байх бүх оройн хосыг олох шаардлагатай болно.
Бодлогын эдгээр хоёр хувилбарыг бодоход өөр өөр алгоритм ашиглах нь тохиромжтой тул бид энд хоёуланг нь авч үзнэ.
Беллман-Фордын алгоритм ашиглах¶
Беллман-Фордын алгоритм нь граф дотор сөрөг жинтэй цикл байгаа эсэхийг шалгах, хэрэв байвал тэдгээр циклийн нэгийг олох боломж олгодог.
Алгоритмын дэлгэрэнгүйг Беллман-Форд алгоритмын тухай өгүүлэлд тайлбарласан. Энд бид зөвхөн энэ бодлогод хэрхэн хэрэглэхийг л тайлбарлана.
Беллман-Фордын стандарт хэрэгжүүлэлт нь эхлэлийн ямар нэг орой $v$-ээс хүрч болох сөрөг циклийг хайдаг; гэхдээ алгоритмыг граф дахь дурын сөрөг циклийг хайхаар өөрчилж болно. Үүний тулд бид бүх зай $d[i]$-г хязгааргүй биш тэгээр эхлүүлэх хэрэгтэй — яг л бид бүх оройноос нэгэн зэрэг хамгийн богино замыг хайж байгаа мэт; энэ нь сөрөг циклийг илрүүлэх зөв байдалд нөлөөлөхгүй.
Беллман-Фордын алгоритмын $N$ итерац хий. Хэрэв сүүлийн итерацад ямар ч өөрчлөлт гараагүй бол граф дотор сөрөг жинтэй цикл байхгүй. Эс бөгөөс зай нь өөрчлөгдсөн оройг аваад, циклийг олох хүртэл түүнээс өвгүүдээр нь дамжин яв. Энэ цикл нь хайж буй сөрөг жинтэй цикл байх болно.
Implementation¶
struct Edge {
int a, b, cost;
};
int n;
vector<Edge> edges;
const int INF = 1000000000;
void solve() {
vector<int> d(n, 0);
vector<int> p(n, -1);
int x;
for (int i = 0; i < n; ++i) {
x = -1;
for (Edge e : edges) {
if (d[e.a] + e.cost < d[e.b]) {
d[e.b] = max(-INF, d[e.a] + e.cost);
p[e.b] = e.a;
x = e.b;
}
}
}
if (x == -1) {
cout << "No negative cycle found.";
} else {
for (int i = 0; i < n; ++i)
x = p[x];
vector<int> cycle;
for (int v = x;; v = p[v]) {
cycle.push_back(v);
if (v == x && cycle.size() > 1)
break;
}
reverse(cycle.begin(), cycle.end());
cout << "Negative cycle: ";
for (int v : cycle)
cout << v << ' ';
cout << endl;
}
}
Флойд-Уоршеллийн алгоритм ашиглах¶
Флойд-Уоршеллийн алгоритм нь бодлогын хоёр дахь хувилбарыг бодох боломж олгодог — хооронд нь хамгийн богино зам байхгүй (өөрөөр хэлбэл дурын бага жинтэй зам оршин байх) бүх оройн хос $(i, j)$-г олох.
Дахин хэлэхэд дэлгэрэнгүйг Флойд-Уоршелл өгүүллээс олж болох ба энд бид зөвхөн хэрхэн хэрэглэхийг л тайлбарлана.
Граф дээр Флойд-Уоршеллийн алгоритмыг ажиллуул.
Эхэндээ $v$ бүрийн хувьд $d[v][v] = 0$ байна.
Гэвч алгоритмыг ажиллуулсны дараа хэрэв $v$-ээс $v$ хүрэх сөрөг урттай зам оршин байвал $d[v][v]$ нь $0$-ээс бага болно.
Үүнийг ашиглан бид хооронд нь хамгийн богино зам байхгүй бүх оройн хосыг ч бас олж чадна.
Бид бүх оройн хос $(i, j)$-г давтан үзэж, хос бүрийн хувьд тэдгээрийн хооронд хамгийн богино зам байгаа эсэхийг шалгана.
Үүний тулд завсрын орой $t$-ийн бүх боломжийг туршиж үз.
Хэрэв завсрын оройнуудын нэг $t$ нь $d[t][t] < 0$ (өөрөөр хэлбэл $t$ нь сөрөг жинтэй циклийн хэсэг) байх ба $i$-ээс $t$ хүрч болох, $t$-ээс $j$ хүрч болох бол $(i, j)$ нь хамгийн богино замгүй.
Тэгвэл $i$-ээс $j$ хүрэх зам дурын бага жинтэй байж болно.
Бид үүнийг -INF гэж тэмдэглэнэ.
Implementation¶
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int t = 0; t < n; ++t) {
if (d[i][t] < INF && d[t][t] < 0 && d[t][j] < INF)
d[i][j] = - INF;
}
}
}