মিনিমাম-কস্ট ফ্লো - সাক্সেসিভ শর্টেস্ট পাথ অ্যালগরিদম#
$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)$ এজের জন্য আমরা নেটওয়ার্কে রিভার্স এজ $(j, i)$ যোগ করি যার ক্যাপাসিটি $U_{j i} = 0$ এবং কস্ট $C_{j i} = -C_{i j}$। যেহেতু, আমাদের শর্তানুযায়ী, $(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$ টি ডিরেক্টেড এজে বিভক্ত করে, এবং আমরা আসলে একটি মাল্টিগ্রাফ পাই।
মাল্টিপল এজ কীভাবে হ্যান্ডেল করব? প্রথমত, প্রতিটি মাল্টিপল এজের ফ্লো আলাদাভাবে রাখতে হবে। দ্বিতীয়ত, শর্টেস্ট পাথ খোঁজার সময়, পাথে কোন মাল্টিপল এজ ব্যবহৃত হচ্ছে তা গুরুত্বপূর্ণ। তাই সাধারণ অ্যানসেস্টর অ্যারের পাশাপাশি আমাদের অতিরিক্তভাবে সেই এজ নম্বরও সংরক্ষণ করতে হবে যেটি থেকে আমরা এসেছি। তৃতীয়ত, একটি নির্দিষ্ট এজ বরাবর ফ্লো বাড়ানোর সময়, ব্যাক এজ বরাবর ফ্লো কমাতে হবে। যেহেতু আমাদের মাল্টিপল এজ আছে, তাই আমাদের প্রতিটি এজের জন্য রিভার্স এজের নম্বর সংরক্ষণ করতে হবে।
আনডিরেক্টেড গ্রাফ বা মাল্টিগ্রাফ নিয়ে এছাড়া আর কোনো বাধা নেই।
কমপ্লেক্সিটি#
এখানে অ্যালগরিদমটি সাধারণত ইনপুটের আকারে এক্সপোনেনশিয়াল। আরো সুনির্দিষ্টভাবে, সবচেয়ে খারাপ ক্ষেত্রে এটি প্রতিটি ইটারেশনে মাত্র $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$ হলো এজগুলোর মধ্যে পাওয়া সর্বোচ্চ কস্ট। পটেনশিয়াল এবং ডিনিক অ্যালগরিদমের সাথে তাদের সমন্বয় সম্পর্কে আরো পড়তে পারেন এখানে।
ইমপ্লিমেন্টেশন#
এখানে সবচেয়ে সরল ক্ষেত্রের জন্য 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;
}