Беллман-Фордын алгоритм¶
Сөрөг жинтэй ирмэгтэй үеийн ганц эхээс гарах хамгийн богино зам
Бидэнд $n$ орой, $m$ ирмэгтэй жинтэй чиглэлтэй граф $G$ ба заасан ямар нэг орой $v$ өгөгдсөн гэж үзье. Та орой $v$-ээс бусад орой бүр хүрэх хамгийн богино замын уртыг олохыг хүсэж байна.
Дейкстрагийн алгоритмаас ялгаатай нь энэ алгоритмыг сөрөг жинтэй ирмэг агуулсан графт ч хэрэглэж болно. Гэвч хэрэв граф сөрөг цикл агуулж байвал зарим орой хүрэх хамгийн богино зам оршихгүй байж болох нь тодорхой (учир нь хамгийн богино замын жин хасах хязгааргүйтэй тэнцүү байх ёстой); гэхдээ энэ алгоритмыг сөрөг жинтэй цикл байгааг мэдэгдэх, эсвэл бүр тэр циклийг гаргаж авахаар өөрчилж болно.
Алгоритм нь Ричард Беллман, Лестер Форд гэсэн хоёр Америк эрдэмтний нэрийг агуулдаг. Форд үнэндээ энэ алгоритмыг 1956 онд өөр нэг математик бодлого судлах явцад зохиосон бөгөөд тэр бодлого эцэстээ граф дахь хамгийн богино замыг олох дэд бодлого болж буурсан ба Форд энэ бодлогыг бодох алгоритмын тоймыг өгсөн. Беллман 1958 онд хамгийн богино зам олох бодлогод тусгайлан зориулсан өгүүлэл нийтэлсэн бөгөөд энэ өгүүлэлд тэрээр алгоритмыг бидэнд одоо мэдэгдэж буй хэлбэрээр нь тодорхой томьёолсон.
Алгоритмын тайлбар¶
Граф сөрөг жинтэй цикл агуулаагүй гэж үзье. Сөрөг жинтэй цикл байгаа тохиолдлыг доор тусад нь хэсэгт авч үзнэ.
Бид алгоритмыг гүйцэтгэсний дараа бодлогын хариуг агуулах зайн массив $d[0 \ldots n-1]$ үүсгэнэ. Эхэндээ бид түүнийг дараах байдлаар дүүргэнэ: $d[v] = 0$, бусад бүх элемент $d[ ]$ нь хязгааргүй $\infty$-тэй тэнцүү.
Алгоритм хэд хэдэн фазаас тогтоно. Фаз бүр графын бүх ирмэгийг шалгах ба алгоритм $c$ жинтэй ирмэг $(a,b)$ бүрийн дагуу сулруулалт хийхийг оролдоно. Ирмэгүүдийн дагуух сулруулалт гэдэг нь $d[a] + c$ утгыг ашиглан $d[b]$ утгыг сайжруулах оролдлого юм. Үнэндээ энэ нь бид ирмэг $(a,b)$ ба орой $a$-ийн одоогийн хариуг ашиглан энэ оройн хариуг сайжруулахыг оролдож байна гэсэн үг.
Граф дахь бүх хамгийн богино замын уртыг зөв тооцоолоход алгоритмын $n-1$ фаз хангалттай гэж батлан хэлдэг (дахин хэлэхэд бид сөрөг жинтэй цикл байхгүй гэж үзэж байна). Хүрэх боломжгүй оройнуудын хувьд зай $d[ ]$ нь хязгааргүй $\infty$-тэй тэнцүү хэвээр үлдэнэ.
Implementation¶
Unlike many other graph algorithms, for Bellman-Ford algorithm, it is more convenient to represent the graph using a single list of all edges (instead of $n$ lists of edges - edges from each vertex). We start the implementation with a structure $\rm edge$ for representing the edges. The input to the algorithm are numbers $n$, $m$, list $e$ of edges and the starting vertex $v$. All the vertices are numbered $0$ to $n - 1$.
The simplest implementation¶
The constant $\rm INF$ denotes the number "infinity" — it should be selected in such a way that it is greater than all possible path lengths.
struct Edge {
int a, b, cost;
};
int n, m, v;
vector<Edge> edges;
const int INF = 1000000000;
void solve()
{
vector<int> d(n, INF);
d[v] = 0;
for (int i = 0; i < n - 1; ++i)
for (Edge e : edges)
if (d[e.a] < INF)
d[e.b] = min(d[e.b], d[e.a] + e.cost);
// display d, for example, on the screen
}
The check if (d[e.a] < INF) is needed only if the graph contains negative weight edges: no such verification would result in relaxation from the vertices to which paths have not yet found, and incorrect distance, of the type $\infty - 1$, $\infty - 2$ etc. would appear.
A better implementation¶
This algorithm can be somewhat speeded up: often we already get the answer in a few phases and no useful work is done in remaining phases, just a waste visiting all edges. So, let's keep the flag, to tell whether something changed in the current phase or not, and if any phase, nothing changed, the algorithm can be stopped. (This optimization does not improve the asymptotic behavior, i.e., some graphs will still need all $n-1$ phases, but significantly accelerates the behavior of the algorithm "on an average", i.e., on random graphs.)
With this optimization, it is generally unnecessary to restrict manually the number of phases of the algorithm to $n-1$ — the algorithm will stop after the desired number of phases.
void solve()
{
vector<int> d(n, INF);
d[v] = 0;
for (;;) {
bool any = false;
for (Edge e : edges)
if (d[e.a] < INF)
if (d[e.b] > d[e.a] + e.cost) {
d[e.b] = d[e.a] + e.cost;
any = true;
}
if (!any)
break;
}
// display d, for example, on the screen
}
Retrieving Path¶
Let us now consider how to modify the algorithm so that it not only finds the length of shortest paths, but also allows to reconstruct the shortest paths.
For that, let's create another array $p[0 \ldots n-1]$, where for each vertex we store its "predecessor", i.e. the penultimate vertex in the shortest path leading to it. In fact, the shortest path to any vertex $a$ is a shortest path to some vertex $p[a]$, to which we added $a$ at the end of the path.
Note that the algorithm works on the same logic: it assumes that the shortest distance to one vertex is already calculated, and, tries to improve the shortest distance to other vertices from that vertex. Therefore, at the time of improvement we just need to remember $p[ ]$, i.e, the vertex from which this improvement has occurred.
Following is an implementation of the Bellman-Ford with the retrieval of shortest path to a given node $t$:
void solve()
{
vector<int> d(n, INF);
d[v] = 0;
vector<int> p(n, -1);
for (;;) {
bool any = false;
for (Edge e : edges)
if (d[e.a] < INF)
if (d[e.b] > d[e.a] + e.cost) {
d[e.b] = d[e.a] + e.cost;
p[e.b] = e.a;
any = true;
}
if (!any)
break;
}
if (d[t] == INF)
cout << "No path from " << v << " to " << t << ".";
else {
vector<int> path;
for (int cur = t; cur != -1; cur = p[cur])
path.push_back(cur);
reverse(path.begin(), path.end());
cout << "Path from " << v << " to " << t << ": ";
for (int u : path)
cout << u << ' ';
}
}
Here starting from the vertex $t$, we go through the predecessors till we reach starting vertex with no predecessor, and store all the vertices in the path in the list $\rm path$. This list is a shortest path from $v$ to $t$, but in reverse order, so we call $\rm reverse()$ function over $\rm path$ and then output the path.
Алгоритмын баталгаа¶
Эхлээд хүрэх боломжгүй бүх орой $u$-ийн хувьд алгоритм зөв ажиллах ба шошго $d[u]$ хязгааргүйтэй тэнцүү хэвээр үлдэхийг анзаар (учир нь Беллман-Фордын алгоритм эхлэлийн орой $v$-ээс хүрч болох бүх орой хүрэх ямар нэг замыг олох ба үлдсэн бусад бүх оройн хувьд сулруулалт хэзээ ч тохиолдохгүй).
Одоо дараах мэдэгдлийг батлая: $i$ дахь фазыг гүйцэтгэсний дараа Беллман-Фордын алгоритм ирмэгийн тоо нь $i$-ээс хэтрэхгүй бүх хамгийн богино замыг зөв олно.
Өөрөөр хэлбэл дурын орой $a$-ийн хувьд түүн хүрэх хамгийн богино зам дахь ирмэгийн тоог $k$ гэж тэмдэглэе (хэрэв ийм зам хэд хэд байвал дурыг нь авч болно). Энэ мэдэгдлийн дагуу алгоритм $k$ дахь фазын дараа орой $a$-ийн хамгийн богино зам олдоно гэдгийг баталгаажуулна.
Баталгаа: Эхлэлийн орой $v$-ээс зам байх дурын орой $a$-г авч үзээд, түүн хүрэх хамгийн богино зам $(p_0=v, p_1, \ldots, p_k=a)$-г авч үзье. Эхний фазаас өмнө орой $p_0 = v$ хүрэх хамгийн богино зам зөв олдсон байсан. Эхний фазын явцад алгоритм ирмэг $(p_0,p_1)$-г шалгасан тул эхний фазын дараа орой $p_1$ хүрэх зай зөв тооцоологдсон. Энэ мэдэгдлийг $k$ удаа давтвал $k$ дахь фазын дараа орой $p_k = a$ хүрэх зай зөв тооцоологддогийг бид харах ба энэ нь бидний батлахыг хүссэн зүйл юм.
Анзаарах сүүлийн зүйл бол дурын хамгийн богино зам $n - 1$-ээс олон ирмэгтэй байж чадахгүй явдал юм. Тиймээс алгоритм $(n-1)$ дэх фаз хүртэл явахад хангалттай. Үүний дараа ямар ч сулруулалт ямар нэг орой хүрэх зайг сайжруулахгүй нь баталгаатай.
Сөрөг циклийн тохиолдол¶
Дээр хаа сайгүй бид графт сөрөг цикл байхгүй гэж үзсэн (яг хэлбэл бид эхлэлийн орой $v$-ээс хүрч болох сөрөг циклийг сонирхож байгаа бөгөөд хүрэх боломжгүй циклийн хувьд дээрх алгоритмд юу ч өөрчлөгдөхгүй). Сөрөг цикл байгаа тохиолдолд энэ цикл дэх бүх орой хүрэх зай, мөн энэ циклээс хүрч болох орой хүрэх зай тодорхойлогдоогүй байдагтай холбоотой нэмэлт хүндрэлүүд гарна — тэдгээр нь хасах хязгааргүй $(- \infty)$-тэй тэнцүү байх ёстой.
Беллман-Фордын алгоритм энэ циклийн бүх орой ба түүнээс хүрч болох оройнуудын дунд сулруулалтыг төгсгөлгүй хийж чадахыг харахад амархан. Тиймээс хэрэв та фазын тоог $n - 1$-ээр хязгаарлахгүй бол алгоритм эдгээр оройноос хүрэх зайг байнга сайжруулсаар хязгааргүй ажиллана.
Эндээс бид эх орой $v$-ээс хүрч болох сөрөг жинтэй цикл байгаа эсэхийн шалгуур-ыг авна: $(n-1)$ дэх фазын дараа хэрэв бид алгоритмыг бас нэг фаз ажиллуулахад дор хаяж бас нэг сулруулалт хийвэл граф $v$-ээс хүрч болох сөрөг жинтэй цикл агуулна; эс бөгөөс ийм цикл оршихгүй.
Түүнээс гадна хэрэв ийм цикл олдвол Беллман-Фордын алгоритмыг энэ циклийг түүнд агуулагдах оройнуудын дараалал болгон гаргаж авахаар өөрчилж болно. Үүний тулд $n$ дэх фазад сулруулалт хийгдсэн сүүлийн орой $x$-г санахад хангалттай. Энэ орой эсвэл сөрөг жинтэй цикл дээр орших, эсвэл түүнээс хүрч болно. Сөрөг цикл дээр орших нь баталгаатай оройнуудыг авахын тулд орой $x$-ээс эхлэн өмнөх оройнуудаар $n$ удаа өнгөр. Ингэснээр бид сөрөг цикл дээр орших нь баталгаатай орой $y$ хүрнэ. Бид энэ оройноос өмнөх оройнуудаар дамжин мөн тэр орой $y$ рүү буцаж очих хүртэл явах ёстой (мөн энэ нь тохиолдох болно, учир нь сөрөг жинтэй цикл дэх сулруулалт тойрог хэлбэрээр явагддаг).
Implementation:¶
void solve()
{
vector<int> d(n, INF);
d[v] = 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] < INF)
if (d[e.b] > d[e.a] + e.cost) {
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 from " << v;
else {
int y = x;
for (int i = 0; i < n; ++i)
y = p[y];
vector<int> path;
for (int cur = y;; cur = p[cur]) {
path.push_back(cur);
if (cur == y && path.size() > 1)
break;
}
reverse(path.begin(), path.end());
cout << "Negative cycle: ";
for (int u : path)
cout << u << ' ';
}
}
Due to the presence of a negative cycle, for $n$ iterations of the algorithm, the distances may go far in the negative range (to negative numbers of the order of $-n m W$, where $W$ is the maximum absolute value of any weight in the graph). Hence in the code, we adopted additional measures against the integer overflow as follows:
d[e.b] = max(-INF, d[e.a] + e.cost);
The above implementation looks for a negative cycle reachable from some starting vertex $v$; however, the algorithm can be modified to just look for any negative cycle in the graph. For this we need to put all the distance $d[i]$ to zero and not infinity — as if we are looking for the shortest path from all vertices simultaneously; the validity of the detection of a negative cycle is not affected.
For more on this topic — see separate article, Finding a negative cycle in the graph.
Хамгийн богино замын хурдан алгоритм (SPFA)¶
SPFA бол сулруулалтын бүх оролдлого амжилттай болдоггүй гэдэг баримтыг ашигладаг Беллман-Фордын алгоритмын сайжруулалт юм. Гол санаа нь сулруулагдсан боловч хөршүүдээ цаашид сулруулж чадах оройнуудыг л агуулсан дараалал үүсгэх явдал юм. Мөн та ямар нэг хөршийг сулруулж чадах бүрд түүнийг дараалалд оруулах хэрэгтэй. Энэ алгоритмыг Беллман-Фордын нэгэн адил сөрөг цикл илрүүлэхэд бас ашиглаж болно.
Энэ алгоритмын хамгийн муу тохиолдол нь Беллман-Фордын $O(n m)$-тэй тэнцүү боловч практикт энэ нь хамаагүй хурдан ажиллах ба зарим хүмүүс энэ нь дунджаар $O(m)$-д ч ажилладаг гэж баталдаг. Гэвч болгоомжтой байгаарай, учир нь энэ алгоритм детерминистик бөгөөд алгоритмыг $O(n m)$-д ажиллуулах эсрэг жишээ үүсгэхэд амархан.
Хэрэгжүүлэлтэд анхаарах ёстой зарим зүйл бий, тухайлбал сөрөг цикл байвал алгоритм үүрд үргэлжилдэг гэдэг баримт. Үүнээс зайлсхийхийн тулд орой хэдэн удаа сулруулагдсаныг хадгалах тоолуур үүсгэж, ямар нэг орой $n$ дахь удаагаа сулруулагдмагц алгоритмыг зогсоох боломжтой. Мөн орой аль хэдийн дараалалд байгаа бол түүнийг дараалалд оруулах шаардлагагүйг анзаар.
const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;
bool spfa(int s, vector<int>& d) {
int n = adj.size();
d.assign(n, INF);
vector<int> cnt(n, 0);
vector<bool> inqueue(n, false);
queue<int> q;
d[s] = 0;
q.push(s);
inqueue[s] = true;
while (!q.empty()) {
int v = q.front();
q.pop();
inqueue[v] = false;
for (auto edge : adj[v]) {
int to = edge.first;
int len = edge.second;
if (d[v] + len < d[to]) {
d[to] = d[v] + len;
if (!inqueue[to]) {
q.push(to);
inqueue[to] = true;
cnt[to]++;
if (cnt[to] > n)
return false; // negative cycle
}
}
}
}
return true;
}
Онлайн шүүгч дэх холбогдох бодлогууд¶
Беллман-Фордын алгоритм ашиглан бодож болох даалгаврын жагсаалт:
- E-OLYMP #1453 "Ford-Bellman" [difficulty: low]
- UVA #423 "MPI Maelstrom" [difficulty: low]
- UVA #534 "Frogger" [difficulty: medium]
- UVA #10099 "The Tourist Guide" [difficulty: medium]
- UVA #515 "King" [difficulty: medium]
- UVA 12519 - The Farnsworth Parabox
Мөн Граф дахь сөрөг циклийг олох өгүүлэл дэх бодлогын жагсаалтыг үз. * CSES - High Score * CSES - Cycle Finding