ম্যাক্সিমাম ফ্লো - ডিনিকের অ্যালগরিদম#
ডিনিকের অ্যালগরিদম ম্যাক্সিমাম ফ্লো সমস্যা $O(V^2E)$ এ সমাধান করে। ম্যাক্সিমাম ফ্লো সমস্যাটি ম্যাক্সিমাম ফ্লো - ফোর্ড-ফুলকারসন এবং এডমন্ডস-কার্প নিবন্ধে সংজ্ঞায়িত করা হয়েছে। এই অ্যালগরিদমটি ইয়েফিম ডিনিৎজ ১৯৭০ সালে আবিষ্কার করেন।
সংজ্ঞাসমূহ#
নেটওয়ার্ক $G$ এর একটি রেসিডুয়াল নেটওয়ার্ক $G^R$ হলো এমন একটি নেটওয়ার্ক যেটি $G$ এর প্রতিটি এজ $(v, u)\in G$ এর জন্য দুটি এজ ধারণ করে:
- $(v, u)$ যার ক্যাপাসিটি $c_{vu}^R = c_{vu} - f_{vu}$
- $(u, v)$ যার ক্যাপাসিটি $c_{uv}^R = f_{vu}$
কোনো নেটওয়ার্কের একটি ব্লকিং ফ্লো হলো এমন একটি ফ্লো যাতে $s$ থেকে $t$ পর্যন্ত প্রতিটি পাথে কমপক্ষে একটি এজ থাকে যেটি এই ফ্লো দ্বারা স্যাচুরেটেড। লক্ষ্য করুন যে একটি ব্লকিং ফ্লো অগত্যা ম্যাক্সিমাল নয়।
একটি নেটওয়ার্ক $G$ এর একটি লেয়ার্ড নেটওয়ার্ক হলো নিম্নলিখিত উপায়ে নির্মিত একটি নেটওয়ার্ক। প্রথমত, প্রতিটি ভার্টেক্স $v$ এর জন্য আমরা $level[v]$ গণনা করি - শুধুমাত্র পজিটিভ ক্যাপাসিটির এজ ব্যবহার করে $s$ থেকে এই ভার্টেক্স পর্যন্ত শর্টেস্ট পাথ (আনওয়েটেড)। তারপর আমরা শুধু সেই এজ $(v, u)$ রাখি যাদের জন্য $level[v] + 1 = level[u]$। স্পষ্টতই, এই নেটওয়ার্কটি অ্যাসাইক্লিক।
অ্যালগরিদম#
অ্যালগরিদমটি কয়েকটি ফেজে গঠিত। প্রতিটি ফেজে আমরা $G$ এর রেসিডুয়াল নেটওয়ার্কের লেয়ার্ড নেটওয়ার্ক তৈরি করি। তারপর আমরা লেয়ার্ড নেটওয়ার্কে একটি ইচ্ছামতো ব্লকিং ফ্লো খুঁজি এবং এটি বর্তমান ফ্লো-তে যোগ করি।
সঠিকতার প্রমাণ#
দেখাই যে অ্যালগরিদম শেষ হলে এটি ম্যাক্সিমাম ফ্লো খুঁজে পায়।
যদি অ্যালগরিদম শেষ হয়ে যায়, তাহলে এটি লেয়ার্ড নেটওয়ার্কে কোনো ব্লকিং ফ্লো খুঁজে পায়নি। এর মানে হলো লেয়ার্ড নেটওয়ার্কে $s$ থেকে $t$ পর্যন্ত কোনো পাথ নেই। এর মানে হলো রেসিডুয়াল নেটওয়ার্কে $s$ থেকে $t$ পর্যন্ত কোনো পাথ নেই। এর মানে হলো ফ্লোটি ম্যাক্সিমাম।
ফেজের সংখ্যা#
অ্যালগরিদম $V$ এর কম ফেজে শেষ হয়। এটি প্রমাণ করতে আমাদের প্রথমে দুটি লেমা প্রমাণ করতে হবে।
লেমা ১। প্রতিটি ইটারেশনের পর $s$ থেকে প্রতিটি ভার্টেক্সের দূরত্ব কমে না, অর্থাৎ $level_{i+1}[v] \ge level_i[v]$।
প্রমাণ। একটি ফেজ $i$ এবং একটি ভার্টেক্স $v$ ঠিক করুন। $G_{i+1}^R$ এ $s$ থেকে $v$ পর্যন্ত যেকোনো শর্টেস্ট পাথ $P$ বিবেচনা করুন। $P$ এর দৈর্ঘ্য $level_{i+1}[v]$ এর সমান। লক্ষ্য করুন যে $G_{i+1}^R$ শুধুমাত্র $G_i^R$ এর এজ এবং $G_i^R$ এর এজের ব্যাক এজ ধারণ করতে পারে। যদি $P$ তে $G_i^R$ এর কোনো ব্যাক এজ না থাকে, তাহলে $level_{i+1}[v] \ge level_i[v]$ কারণ $P$ $G_i^R$ এও একটি পাথ। এখন ধরি $P$ তে কমপক্ষে একটি ব্যাক এজ আছে। প্রথম এমন এজটি হোক $(u, w)$। তখন $level_{i+1}[u] \ge level_i[u]$ (প্রথম ক্ষেত্রের কারণে)। এজ $(u, w)$ $G_i^R$ এ নেই, তাই এজ $(w, u)$ পূর্ববর্তী ইটারেশনে ব্লকিং ফ্লো দ্বারা প্রভাবিত হয়েছে। এর মানে $level_i[u] = level_i[w] + 1$। এছাড়া, $level_{i+1}[w] = level_{i+1}[u] + 1$। এই দুটি সমীকরণ এবং $level_{i+1}[u] \ge level_i[u]$ থেকে আমরা পাই $level_{i+1}[w] \ge level_i[w] + 2$। এখন আমরা পাথের বাকি অংশের জন্য একই ধারণা ব্যবহার করতে পারি।
লেমা ২। $level_{i+1}[t] > level_i[t]$
প্রমাণ। পূর্ববর্তী লেমা থেকে, $level_{i+1}[t] \ge level_i[t]$। ধরি $level_{i+1}[t] = level_i[t]$। লক্ষ্য করুন যে $G_{i+1}^R$ শুধুমাত্র $G_i^R$ এর এজ এবং $G_i^R$ এর এজের ব্যাক এজ ধারণ করতে পারে। এর মানে $G_i^R$ এ একটি শর্টেস্ট পাথ আছে যেটি ব্লকিং ফ্লো দ্বারা ব্লক করা হয়নি। এটি একটি বৈপরীত্য।
এই দুটি লেমা থেকে আমরা সিদ্ধান্তে আসি যে $V$ এর কম ফেজ আছে কারণ $level[t]$ বাড়ে, কিন্তু এটি $V - 1$ এর চেয়ে বেশি হতে পারে না।
ব্লকিং ফ্লো খোঁজা#
প্রতিটি ইটারেশনে ব্লকিং ফ্লো খুঁজতে, আমরা কেবল লেয়ার্ড নেটওয়ার্কে $s$ থেকে $t$ পর্যন্ত DFS দিয়ে ফ্লো পুশ করার চেষ্টা করতে পারি যতক্ষণ পুশ করা যায়। এটি আরও দ্রুত করতে, আমাদের সেই এজগুলো সরাতে হবে যেগুলো আর পুশ করতে ব্যবহার করা যায় না। এটি করতে আমরা প্রতিটি ভার্টেক্সে একটি পয়েন্টার রাখতে পারি যেটি পরবর্তী ব্যবহারযোগ্য এজকে নির্দেশ করে।
একটি একক DFS রান $O(k+V)$ সময় নেয়, যেখানে $k$ হলো এই রানে পয়েন্টার অ্যাডভান্সের সংখ্যা। সমস্ত রানে মোট পয়েন্টার অ্যাডভান্সের সংখ্যা $E$ অতিক্রম করতে পারে না। অন্যদিকে, মোট রানের সংখ্যা $E$ অতিক্রম করবে না, যেহেতু প্রতিটি রান কমপক্ষে একটি এজ স্যাচুরেট করে। এভাবে, ব্লকিং ফ্লো খুঁজতে মোট রানিং টাইম $O(VE)$।
কমপ্লেক্সিটি#
$V$ এর কম ফেজ আছে, তাই মোট কমপ্লেক্সিটি $O(V^2E)$।
ইউনিট নেটওয়ার্ক#
একটি ইউনিট নেটওয়ার্ক হলো এমন একটি নেটওয়ার্ক যেখানে $s$ এবং $t$ ব্যতীত যেকোনো ভার্টেক্সের জন্য হয় ইনকামিং বা আউটগোয়িং এজ অনন্য এবং ইউনিট ক্যাপাসিটি বিশিষ্ট। এটি ঠিক সেই ক্ষেত্র যেটি আমরা ফ্লো দিয়ে ম্যাক্সিমাম ম্যাচিং সমস্যা সমাধান করতে নেটওয়ার্ক তৈরি করি।
ইউনিট নেটওয়ার্কে ডিনিকের অ্যালগরিদম $O(E\sqrt{V})$ এ কাজ করে। এটি প্রমাণ করি।
প্রথমত, প্রতিটি ফেজ এখন $O(E)$ তে কাজ করে কারণ প্রতিটি এজ সর্বাধিক একবার বিবেচিত হবে।
দ্বিতীয়ত, ধরি ইতিমধ্যে $\sqrt{V}$ টি ফেজ হয়ে গেছে। তখন $\le\sqrt{V}$ দৈর্ঘ্যের সমস্ত অগমেন্টিং পাথ পাওয়া গেছে। $f$ কে বর্তমান ফ্লো, $f'$ কে ম্যাক্সিমাম ফ্লো হতে দিন। তাদের পার্থক্য $f' - f$ বিবেচনা করুন। এটি $G^R$ এ $|f'| - |f|$ মানের একটি ফ্লো এবং প্রতিটি এজে এটি হয় $0$ বা $1$। এটি $|f'| - |f|$ টি $s$ থেকে $t$ পাথ এবং সম্ভবত সাইকেলে বিভক্ত করা যায়। যেহেতু নেটওয়ার্ক ইউনিট, তাদের কমন ভার্টেক্স থাকতে পারে না, তাই মোট ভার্টেক্স সংখ্যা $\ge (|f'| - |f|)\sqrt{V}$, কিন্তু এটি $\le V$ ও, তাই আরও $\sqrt{V}$ ইটারেশনে আমরা অবশ্যই ম্যাক্সিমাম ফ্লো পাব।
ইউনিট ক্যাপাসিটি নেটওয়ার্ক#
আরও সাধারণ সেটিংয়ে যখন সব এজের ইউনিট ক্যাপাসিটি আছে, কিন্তু ইনকামিং এবং আউটগোয়িং এজের সংখ্যা সীমাহীন, পাথগুলোর কমন ভার্টেক্সের বদলে কমন এজ থাকতে পারে না। একইভাবে ইটারেশন সংখ্যার উপর $\sqrt E$ বাউন্ড প্রমাণ করা যায়, তাই এমন নেটওয়ার্কে ডিনিক অ্যালগরিদমের রানিং টাইম সর্বাধিক $O(E \sqrt E)$।
পরিশেষে, এটিও প্রমাণ করা সম্ভব যে ইউনিট ক্যাপাসিটি নেটওয়ার্কে ফেজের সংখ্যা $O(V^{2/3})$ অতিক্রম করে না, যা বিশেষভাবে বেশি এজ সংখ্যা বিশিষ্ট নেটওয়ার্কে $O(EV^{2/3})$ এর একটি বিকল্প অনুমান প্রদান করে।
ইমপ্লিমেন্টেশন#
struct FlowEdge {
int v, u;
long long cap, flow = 0;
FlowEdge(int v, int u, long long cap) : v(v), u(u), cap(cap) {}
};
struct Dinic {
const long long flow_inf = 1e18;
vector<FlowEdge> edges;
vector<vector<int>> adj;
int n, m = 0;
int s, t;
vector<int> level, ptr;
queue<int> q;
Dinic(int n, int s, int t) : n(n), s(s), t(t) {
adj.resize(n);
level.resize(n);
ptr.resize(n);
}
void add_edge(int v, int u, long long cap) {
edges.emplace_back(v, u, cap);
edges.emplace_back(u, v, 0);
adj[v].push_back(m);
adj[u].push_back(m + 1);
m += 2;
}
bool bfs() {
while (!q.empty()) {
int v = q.front();
q.pop();
for (int id : adj[v]) {
if (edges[id].cap == edges[id].flow)
continue;
if (level[edges[id].u] != -1)
continue;
level[edges[id].u] = level[v] + 1;
q.push(edges[id].u);
}
}
return level[t] != -1;
}
long long dfs(int v, long long pushed) {
if (pushed == 0)
return 0;
if (v == t)
return pushed;
for (int& cid = ptr[v]; cid < (int)adj[v].size(); cid++) {
int id = adj[v][cid];
int u = edges[id].u;
if (level[v] + 1 != level[u])
continue;
long long tr = dfs(u, min(pushed, edges[id].cap - edges[id].flow));
if (tr == 0)
continue;
edges[id].flow += tr;
edges[id ^ 1].flow -= tr;
return tr;
}
return 0;
}
long long flow() {
long long f = 0;
while (true) {
fill(level.begin(), level.end(), -1);
level[s] = 0;
q.push(s);
if (!bfs())
break;
fill(ptr.begin(), ptr.end(), 0);
while (long long pushed = dfs(s, flow_inf)) {
f += pushed;
}
}
return f;
}
};