جریان با کمترین هزینه - الگوریتم مسیرهای کوتاه‌تر متوالی¶
شبکه $G$ با $n$ رأس و $m$ یال داده شده است. برای هر یال (به‌طور کلی یال‌های جهت‌دار، اما در ادامه توضیح داده می‌شود)، ظرفیت (یک عدد صحیح نامنفی) و هزینه به ازای هر واحد جریان در طول آن یال (یک عدد صحیح) مشخص شده است. همچنین، منبع $s$ و چاهک $t$ نیز مشخص شده‌اند.
برای یک مقدار داده شده $K$، باید جریانی با این مقدار پیدا کنیم و از بین تمام جریان‌های با این مقدار، جریانی را انتخاب کنیم که کمترین هزینه را داشته باشد. این مسئله، مسئله جریان با کمترین هزینه (minimum-cost flow) نامیده می‌شود.
گاهی اوقات، مسئله کمی متفاوت تعریف می‌شود: می‌خواهیم بیشترین جریان را پیدا کنیم و از بین تمام جریان‌های بیشینه، آنی را بیابیم که کمترین هزینه را دارد. این مسئله، مسئله جریان بیشینه با کمترین هزینه (minimum-cost maximum-flow) نامیده می‌شود.
هر دوی این مسائل را می‌توان به طور مؤثر با الگوریتم مسیرهای کوتاه‌تر متوالی حل کرد.
الگوریتم¶
این الگوریتم شباهت زیادی به الگوریتم Edmonds-Karp برای محاسبه بیشترین جریان دارد.
ساده‌ترین حالت¶
ابتدا ساده‌ترین حالت را در نظر می‌گیریم که در آن گراف جهت‌دار است و بین هر جفت رأس حداکثر یک یال وجود دارد (مثلاً اگر $(i, j)$ یک یال در گراف باشد، آنگاه $(j, i)$ نمی‌تواند بخشی از آن باشد).
فرض کنید $U_{i j}$ ظرفیت یال $(i, j)$ باشد (اگر این یال وجود داشته باشد). و $C_{i j}$ هزینه به ازای هر واحد جریان در طول این یال $(i, j)$ باشد. و در نهایت $F_{i, j}$ جریان در طول یال $(i, j)$ باشد. در ابتدا، تمام مقادیر جریان صفر هستند.
ما شبکه را به صورت زیر تغییر می‌دهیم: به ازای هر یال $(i, j)$، یال معکوس $(j, i)$ را با ظرفیت $U_{j i} = 0$ و هزینه $C_{j i} = -C_{i j}$ به شبکه اضافه می‌کنیم. از آنجایی که طبق محدودیت‌های ما، یال $(j, i)$ قبلاً در شبکه وجود نداشت، همچنان شبکه‌ای داریم که یک چندگراف (گرافی با یال‌های چندگانه) نیست. علاوه بر این، در طول مراحل الگوریتم، همیشه شرط $F_{j i} = -F_{i j}$ را برقرار نگه می‌داریم.
ما شبکه باقیمانده را برای یک جریان ثابت $F$ به صورت زیر تعریف می‌کنیم (درست مانند الگوریتم Ford-Fulkerson): شبکه باقیمانده فقط شامل یال‌های اشباع‌نشده است (یعنی یال‌هایی که در آنها $F_{i j} < U_{i j}$ است) و ظرفیت باقیمانده هر چنین یالی برابر است با $R_{i j} = U_{i j} - F_{i j}$.
اکنون می‌توانیم در مورد الگوریتم محاسبه جریان با کمترین هزینه صحبت کنیم. در هر تکرار الگوریتم، کوتاه‌ترین مسیر را در گراف باقیمانده از $s$ به $t$ پیدا می‌کنیم. برخلاف الگوریتم Edmonds-Karp، ما به دنبال کوتاه‌ترین مسیر از نظر هزینه مسیر هستیم، نه تعداد یال‌ها. اگر دیگر مسیری وجود نداشته باشد، الگوریتم خاتمه می‌یابد و جریان $F$ همان جریان مورد نظر است. اگر مسیری پیدا شد، جریان را در طول آن تا حد امکان افزایش می‌دهیم (یعنی حداقل ظرفیت باقیمانده $R$ در مسیر را پیدا کرده، جریان را به آن مقدار افزایش داده و در یال‌های معکوس متناظر نیز تغییرات لازم را اعمال می‌کنیم). اگر در نقطه‌ای، جریان به مقدار $K$ رسید، الگوریتم را متوقف می‌کنیم (توجه داشته باشید که در آخرین تکرار الگوریتم، لازم است جریان را فقط به اندازه‌ای افزایش دهیم که مقدار جریان نهایی از $K$ بیشتر نشود).
مشاهده این نکته دشوار نیست که اگر $K$ را برابر با بی‌نهایت قرار دهیم، الگوریتم، جریان بیشینه با کمترین هزینه را پیدا خواهد کرد. بنابراین هر دو نوع مسئله را می‌توان با همین الگوریتم حل کرد.
گراف‌های غیرجهت‌دار / چندگراف‌ها¶
حالت گراف غیرجهت‌دار یا چندگراف از نظر مفهومی با الگوریتم بالا تفاوتی ندارد. این الگوریتم روی این گراف‌ها نیز کار می‌کند. با این حال، پیاده‌سازی آن کمی دشوارتر می‌شود.
یک یال غیرجهت‌دار $(i, j)$ در واقع معادل دو یال جهت‌دار $(i, j)$ و $(j, i)$ با ظرفیت و هزینه یکسان است. از آنجایی که الگوریتم جریان با کمترین هزینه که در بالا توصیف شد برای هر یال جهت‌دار یک یال معکوس ایجاد می‌کند، یک یال غیرجهت‌دار به ۴ یال جهت‌دار تقسیم می‌شود و در نتیجه یک چندگراف به دست می‌آید.
چگونه با یال‌های چندگانه برخورد کنیم؟ اولاً، جریان برای هر یک از یال‌های چندگانه باید به طور جداگانه نگهداری شود. ثانیاً، هنگام جستجوی کوتاه‌ترین مسیر، باید در نظر داشت که مهم است کدام یک از یال‌های چندگانه در مسیر استفاده می‌شود. بنابراین، علاوه بر آرایه معمول والد (ancestor)، باید شماره یالی را که از طریق آن به رأس فعلی رسیده‌ایم نیز همراه با والد ذخیره کنیم. ثالثاً، با افزایش جریان در طول یک یال مشخص، لازم است جریان در طول یال معکوس آن کاهش یابد. از آنجایی که یال‌های چندگانه داریم، باید برای هر یال، شماره یال معکوس آن را نیز ذخیره کنیم.
هیچ مانع دیگری در مورد گراف‌های غیرجهت‌دار یا چندگراف‌ها وجود ندارد.
پیچیدگی¶
این الگوریتم به طور کلی نسبت به اندازه ورودی نمایی است. به طور دقیق‌تر، در بدترین حالت ممکن است در هر تکرار تنها به اندازه $1$ واحد جریان ارسال کند، که برای پیدا کردن جریان با کمترین هزینه به اندازه $F$، به $O(F)$ تکرار نیاز دارد. این امر زمان اجرای کلی را به $O(F \cdot T)$ می‌رساند، که در آن $T$ زمان لازم برای یافتن کوتاه‌ترین مسیر از منبع به چاهک است.
اگر از الگوریتم Bellman-Ford برای این کار استفاده شود، زمان اجرا $O(F mn)$ خواهد بود. همچنین می‌توان الگوریتم Dijkstra را طوری تغییر داد که به عنوان یک گام اولیه به $O(nm)$ پیش‌پردازش نیاز داشته باشد و سپس در هر تکرار در زمان $O(m \log n)$ کار کند، که زمان اجرای کلی را به $O(mn + F m \log n)$ می‌رساند. اینجا یک مولد گراف وجود دارد که چنین الگوریتمی روی آن به زمان $O(2^{n/2} n^2 \log n)$ نیاز خواهد داشت.
الگوریتم Dijkstraی تغییریافته از چیزی به نام پتانسیل‌ها از الگوریتم Johnson استفاده می‌کند. می‌توان ایده‌های این الگوریتم و الگوریتم Dinic را ترکیب کرد تا تعداد تکرارها را از $F$ به $\min(F, nC)$ کاهش داد، که در آن $C$ بیشترین هزینه یافت‌شده در میان یال‌ها است. می‌توانید در مورد پتانسیل‌ها و ترکیب آنها با الگوریتم Dinic اینجا بیشتر بخوانید.
پیاده‌سازی¶
در اینجا یک پیاده‌سازی با استفاده از الگوریتم SPFA برای ساده‌ترین حالت آورده شده است.
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;
}