Хамгийн бага өртөгтэй урсгал - Дараалсан хамгийн богино замын алгоритм¶
$n$ орой, $m$ ирмэгээс тогтох сүлжээ $G$ өгөгдсөн. Ирмэг бүрийн хувьд (ерөнхийдөө чиглэлтэй ирмэг, гэхдээ доороос үзнэ үү) багтаамж (сөрөг биш бүхэл тоо) ба энэ ирмэгийн дагуух урсгалын нэгжид ногдох өртөг (ямар нэг бүхэл тоо) өгөгдсөн. Мөн эх $s$ ба цорго $t$ тэмдэглэгдсэн.
Өгөгдсөн утга $K$-ийн хувьд бид энэ хэмжээний урсгалыг олох ёстой ба энэ хэмжээний бүх урсгалын дотроос хамгийн бага өртөгтэйг нь сонгох ёстой. Энэ даалгаврыг хамгийн бага өртөгтэй урсгалын бодлого гэж нэрлэдэг.
Заримдаа даалгаврыг арай өөрөөр өгдөг: та хамгийн их урсгалыг олохыг хүсэх ба бүх максимал урсгалын дотроос хамгийн бага өртөгтэйг нь олохыг хүснэ. Үүнийг хамгийн бага өртөгтэй хамгийн их урсгалын бодлого гэж нэрлэдэг.
Эдгээр хоёр бодлогыг хоёуланг нь дараалсан хамгийн богино замын алгоритмаар үр дүнтэй бодож болно.
Алгоритм¶
Энэ алгоритм хамгийн их урсгалыг тооцоолох Эдмондс-Карп-тай маш төстэй.
Хамгийн энгийн тохиолдол¶
Эхлээд бид граф чиглэлтэй бөгөөд дурын оройн хосын хооронд хамгийн ихдээ нэг ирмэг байх хамгийн энгийн тохиолдлыг л авч үзнэ (жишээ нь хэрэв $(i, j)$ нь граф дахь ирмэг бол $(j, i)$ мөн түүний хэсэг байж чадахгүй).
$U_{i j}$ нь ирмэг $(i, j)$ оршин байвал түүний багтаамж байг. Мөн $C_{i j}$ нь энэ ирмэг $(i, j)$-ийн дагуух урсгалын нэгжид ногдох өртөг байг. Эцэст нь $F_{i, j}$ нь ирмэг $(i, j)$-ийн дагуух урсгал байг. Эхэндээ бүх урсгалын утга тэг байна.
Бид сүлжээг дараах байдлаар өөрчилнө: ирмэг $(i, j)$ бүрийн хувьд бид сүлжээнд $U_{j i} = 0$ багтаамжтай, $C_{j i} = -C_{i j}$ өртөгтэй урвуу ирмэг $(j, i)$-г нэмнэ. Бидний хязгаарлалтын дагуу ирмэг $(j, i)$ өмнө нь сүлжээнд байгаагүй тул бид мультиграф (олон ирмэгтэй граф) биш сүлжээтэй хэвээр байна. Түүнчлэн бид алгоритмын алхмуудын явцад $F_{j i} = -F_{i j}$ нөхцөлийг үргэлж үнэн байлгана.
Бид ямар нэг тогтмол урсгал $F$-ийн хувьд үлдэгдэл сүлжээ-г дараах байдлаар тодорхойлно (яг Форд-Фалкерсоны алгоритм дахьтай адил): үлдэгдэл сүлжээ нь зөвхөн ханаагүй ирмэгүүдийг (өөрөөр хэлбэл $F_{i j} < U_{i j}$ байх ирмэгүүдийг) агуулах ба ийм ирмэг бүрийн үлдэгдэл багтаамж нь $R_{i j} = U_{i j} - F_{i j}$ байна.
Одоо бид хамгийн бага өртөгтэй урсгалыг тооцоолох алгоритмын тухай ярьж болно. Алгоритмын итерац бүрд бид үлдэгдэл граф дахь $s$-ээс $t$ хүрэх хамгийн богино замыг олно. Эдмондс-Карпаас ялгаатай нь бид ирмэгийн тооны оронд замын өртгийн хувьд хамгийн богино замыг хайна. Хэрэв цаашид зам байхгүй бол алгоритм дуусах ба урсгал $F$ нь хайж байсан урсгал болно. Хэрэв зам олдвол бид түүний дагуух урсгалыг аль болох ихээр нэмэгдүүлнэ (өөрөөр хэлбэл бид замын хамгийн бага үлдэгдэл багтаамж $R$-г олж, урсгалыг түүгээр нэмэгдүүлж, буцах ирмэгүүдийг ижил хэмжээгээр бууруулна). Хэрэв ямар нэг үед урсгал $K$ утгад хүрвэл бид алгоритмыг зогсооно (алгоритмын сүүлийн итерацад эцсийн урсгалын утга $K$-аас хэтрэхгүй байхаар л урсгалыг нэмэгдүүлэх шаардлагатайг анхаарна уу).
Хэрэв бид $K$-г хязгааргүй болговол алгоритм хамгийн бага өртөгтэй хамгийн их урсгалыг олно гэдгийг харахад хэцүү биш. Тиймээс бодлогын хоёр хувилбарыг хоёуланг нь ижил алгоритмаар бодож болно.
Чиглэлгүй граф / мультиграф¶
Чиглэлгүй граф эсвэл мультиграфын тохиолдол дээрх алгоритмаас үзэл баримтлалын хувьд ялгаагүй. Алгоритм эдгээр граф дээр ч ажиллана. Гэвч түүнийг хэрэгжүүлэхэд арай хэцүү болно.
Чиглэлгүй ирмэг $(i, j)$ нь үнэндээ ижил багтаамж ба утгатай хоёр чиглэлтэй ирмэг $(i, j)$ ба $(j, i)$-тай ижил юм. Дээр тайлбарласан хамгийн бага өртөгтэй урсгалын алгоритм чиглэлтэй ирмэг бүрийн хувьд буцах ирмэг үүсгэдэг тул энэ нь чиглэлгүй ирмэгийг $4$ чиглэлтэй ирмэг болгон хуваах ба бид үнэндээ мультиграф авна.
Бид олон ирмэг-тэй хэрхэн харьцах вэ? Эхлээд олон ирмэг тус бүрийн урсгалыг тусад нь хадгалах ёстой. Хоёрдугаарт хамгийн богино замыг хайхдаа олон ирмэгийн аль нь замд ашиглагдаж байгаа нь чухал гэдгийг анхаарах шаардлагатай. Тиймээс ердийн өвгийн массивын оронд бид өвгийн хамт аль ирмэгээс ирснийг заасан ирмэгийн дугаарыг нэмж хадгалах ёстой. Гуравдугаарт тодорхой ирмэгийн дагуу урсгал нэмэгдэхэд буцах ирмэгийн дагуух урсгалыг бууруулах шаардлагатай. Бидэнд олон ирмэг байгаа тул бид ирмэг бүрийн хувьд урвуу ирмэгийн ирмэгийн дугаарыг хадгалах ёстой.
Чиглэлгүй граф эсвэл мультиграфтай холбоотой өөр ямар ч саад байхгүй.
Complexity¶
Энд байгаа алгоритм ерөнхийдөө оролтын хэмжээний хувьд экспоненциал байна. Тодруулбал хамгийн муу тохиолдолд энэ нь итерац бүрд ердөө $1$ нэгж урсгал түлхэж болох ба $F$ хэмжээтэй хамгийн бага өртөгтэй урсгалыг олоход $O(F)$ итерац шаардагдаж, нийт ажиллах хугацаа $O(F \cdot T)$ болно, энд $T$ нь эхээс цорго хүрэх хамгийн богино замыг олоход шаардагдах хугацаа юм.
Хэрэв үүнд Беллман-Форд алгоритмыг ашиглавал ажиллах хугацаа $O(F mn)$ болно. Мөн Дейкстрагийн алгоритм-ыг эхний алхам болгон $O(nm)$ урьдчилсан боловсруулалт шаардаж, дараа нь итерац бүрд $O(m \log n)$-д ажиллахаар өөрчилж болох ба ингэснээр нийт ажиллах хугацаа $O(mn + F m \log n)$ болно. Энд ийм алгоритм $O(2^{n/2} n^2 \log n)$ хугацаа шаардах графын генератор байна.
Өөрчилсөн Дейкстрагийн алгоритм Жонсоны алгоритм-аас гаралтай потенциал гэгчийг ашигладаг. Энэ алгоритмын санаа ба Диникийн алгоритмыг хослуулж итерацын тоог $F$-ээс $\min(F, nC)$ болгон бууруулах боломжтой, энд $C$ нь ирмэгүүдийн дундах хамгийн их өртөг юм. Потенциал ба тэдгээрийг Диникийн алгоритмтай хослуулах тухай эндээс цааш уншиж болно.
Implementation¶
Here is an implementation using the SPFA algorithm for the simplest case.
struct Edge
{
int from, to, capacity, cost;
};
vector<vector<int>> adj, cost, capacity;
const int INF = 1e9;
void shortest_paths(int n, int v0, vector<int>& d, vector<int>& p) {
d.assign(n, INF);
d[v0] = 0;
vector<bool> inq(n, false);
queue<int> q;
q.push(v0);
p.assign(n, -1);
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for (int v : adj[u]) {
if (capacity[u][v] > 0 && d[v] > d[u] + cost[u][v]) {
d[v] = d[u] + cost[u][v];
p[v] = u;
if (!inq[v]) {
inq[v] = true;
q.push(v);
}
}
}
}
}
int min_cost_flow(int N, vector<Edge> edges, int K, int s, int t) {
adj.assign(N, vector<int>());
cost.assign(N, vector<int>(N, 0));
capacity.assign(N, vector<int>(N, 0));
for (Edge e : edges) {
adj[e.from].push_back(e.to);
adj[e.to].push_back(e.from);
cost[e.from][e.to] = e.cost;
cost[e.to][e.from] = -e.cost;
capacity[e.from][e.to] = e.capacity;
}
int flow = 0;
int cost = 0;
vector<int> d, p;
while (flow < K) {
shortest_paths(N, s, d, p);
if (d[t] == INF)
break;
// find max flow on that path
int f = K - flow;
int cur = t;
while (cur != s) {
f = min(f, capacity[p[cur]][cur]);
cur = p[cur];
}
// apply flow
flow += f;
cost += f * d[t];
cur = t;
while (cur != s) {
capacity[p[cur]][cur] -= f;
capacity[cur][p[cur]] += f;
cur = p[cur];
}
}
if (flow < K)
return -1;
else
return cost;
}