নেটওয়ার্ক ফ্লো৯ মিনিট পড়া

ডিনিকের অ্যালগরিদম (Dinic's Algorithm)

এক ধাপে সমস্ত ক্ষুদ্রতম অগমেন্টিং পাথগুলো (augmenting paths) একসাথে বা ব্যাচে (batch) সম্পন্ন করে — যা একটি একটি করে বের করার চেয়ে নাটকীয়ভাবে দ্রুতগতির
general:\(O(V^2E)\)unit capacity:\(O(E\sqrt{V})\)bipartite:\(O(E\sqrt{V})\)

ধরুন আপনি কিছু প্যাকেজ শিপিং বা পাঠাচ্ছেন এবং আপনি গুদামঘর বা ওয়্যারহাউস থেকে ডেলিভারি হাব (delivery hub) পর্যন্ত ডেলিভারির সম্ভাব্য প্রতিটি সবচেয়ে ছোট রুট বা রুট (route) খুঁজে পেয়েছেন। এডমন্ডস-কার্প (Edmonds-Karp) অ্যালগরিদম প্যাকেজগুলোকে একটি একটি রুট ধরে পাঠায়, এবং তারপর আবার সবকিছু পুনরায় পরীক্ষা করে বা রি-চেক (re-checks) করে। অন্যদিকে ডিনিকের (Dinic's) কথা হলো: সমস্ত সবচেয়ে ছোট রুট বা রুট (shortest routes) দিয়ে একইসাথে প্যাকেজগুলোকে পাঠান, এবং তারপর পুনরায় মূল্যায়ন বা রি-ইভ্যালুয়েশন (re-evaluate) করুন। আর এটিই হলো এর পেছনের মূল ধারণা।

এই ব্যাচ বা এক ধাপে সম্পন্ন করা পদ্ধতিটিকে মূলত একটি ব্লকিং ফ্লো (blocking flow) বা বাধাদানকারী প্রবাহ বলা হয় — যা বাস্তবে ডিনিকের (Dinic's) অ্যালগরিদমকে চমৎকারভাবে দ্রুতগতি সম্পন্ন করে তোলে এবং থিওরি বা তত্ত্বগতভাবেও একে আরও উন্নত করে তোলে বা বেটার (better) প্রমাণ করে।

1ম পর্যায়: লেভেল গ্রাফ তৈরি করা (Phase 1: Build the Level Graph) (BFS)

প্রতিটি পর্যায় বা ফেজকে (phase) সোর্স বা উৎস s থেকে রেসিডুয়াল গ্রাফ (residual graph) এর দিকে একটি BFS দিয়ে শুরু করুন। এরপর প্রতিটি ভার্টেক্সে (vertex) লেভেল (level) নির্ধারণ করুন যা মূলত এজ বা প্রান্তের (edges) সংখ্যায় s থেকে এর দূরত্বের সমান।

এই লেভেল গ্রাফ (level graph) টি শুধুমাত্র সেই এজগুলিকেই (u→v) ধরে রাখে যেখানে level[v] = level[u] + 1 — এগুলো হলো সেই এজগুলো যা মূলত সিঙ্কের (sink) দিকে কঠোরভাবে এগিয়ে নিয়ে যায়। লেভেল গ্রাফের সমস্ত s-t পাথ বা পথের (paths) ন্যূনতম দৈর্ঘ্যটি সমান বা একই হতে হয়। আর যদি সিঙ্ক t পৌঁছানো না যায় (unreachable), তবে ধরে নিতে হবে যে অ্যালগরিদমটি তার কাজ বন্ধ করে দিয়েছে (কারণ তখন ম্যাক্স ফ্লো (max flow) বা সর্বোচ্চ প্রবাহটি পাওয়া হয়ে গিয়েছে)।

২য় পর্যায়: একটি ব্লকিং ফ্লো খোঁজা বা ফাইন্ড করা (Phase 2: Find a Blocking Flow) (DFS)

একটি ব্লকিং ফ্লো বা বাধাদানকারী প্রবাহ হলো মূলত লেভেল গ্রাফের (level graph) এমন একটি ফ্লো বা প্রবাহ যেখানে প্রত্যেকটি s-t পাথে কমপক্ষে একটি করে স্যাচুরেটেড এজ (saturated edge) বা পরিপৃক্ত প্রান্ত থাকে। একটি ব্লকিং ফ্লো পাঠানোর পরে, লেভেল গ্রাফে কোনো s-t পাথ আর অবশিষ্ট থাকে না — যা পরবর্তী BFS কলটিকে আরও লম্বা পাথ বা পথ (longer paths) খুঁজে বের করতে বাধ্য করে।

এই ব্লকিং ফ্লো-টি খুঁজতে একটি "ডেড এন্ড" অপ্টিমাইজেশন (dead end optimization) সহ মূলত DFS ব্যবহার করা হয়: যখন আপনি এমন একটি ডেড এন্ডে বা মৃত প্রান্তে (যেখানে যাওয়ার জন্য আর কোনো সামনের দিকের এজ বাকি থাকে না) পৌঁছবেন তখন লেভেল গ্রাফ বা level graph থেকে সেই ভার্টেক্সটিকে মুছে ফেলবেন বা ডিলিট করবেন, যাতে আপনি আর কখনোই সেই পাতায় ফিরে যাবেন না বা চেষ্টা করবেন না। যখন আপনি t এ পৌঁছাবেন, তখন পাথ বরাবর ফ্লো বা প্রবাহটি (flow) পিছনের দিকে পাঠান, যা এর বটলনেক (bottleneck) এজটিকে স্যাচুরেট (saturating) করবে বা ভর্তি করবে। প্রতিটি এজ সর্বাধিক একবার ডিলিট বা মুছে ফেলা হয়, যার কারণে পুরো ব্লকিং ফ্লো পর্যায়টি বা ফেজটি সম্পন্ন করতে মোট খরচের পরিমাণ হয় \(O(VE)\)।

কেন প্রতিটি পর্যায়ে (Phase) পাথ বা পথের দৈর্ঘ্য (Path Length) বৃদ্ধি পায়

একটি ব্লকিং ফ্লো বা প্রবাহ (blocking flow) সম্পন্ন হবার পর, বর্তমান লেভেল গ্রাফের (level graph) সমস্ত s-t পাথগুলো ভেঙে ফেলা হয়। এর পরবর্তী BFS কলটিকে অবশ্যই একটি কঠোরভাবে দীর্ঘতর শর্টেস্ট পাথ (longest shortest path) খুঁজে পেতে হবে। যেহেতু পাথের দৈর্ঘ্যগুলো সর্বাধিক V-1 পর্যন্ত হতে পারে, তাই এতে সর্বোচ্চ \(O(V)\) টি পর্যায় বা ফেজ (phases) থাকতে পারে।

প্রতিটি পর্যায়ে: একটি BFS = \(O(E)\) এবং একটি ব্লকিং ফ্লো বা ফ্লো = \(O(VE)\) হয়ে থাকে। সর্বমোট: \(O(V)\) × \(O(VE)\) = \(O(V^2E)\)।

ইউনিট ক্যাপাসিটি নেটওয়ার্ক ও বাইপার্টাইট ম্যাচিং (Unit Capacity Networks and Bipartite Matching)

যখন সমস্ত ক্যাপাসিটিগুলোর বা ক্ষমতার মান 1 হয়, তখন ব্লকিং ফ্লো-গুলো (blocking flows) এজগুলোকে খুব দ্রুত স্যাচুরেট (saturate) বা ভর্তি করে ফেলে এবং পাথের (path) দৈর্ঘ্য আরও দ্রুতগতিতে বৃদ্ধি পায়। পর্যায় বা ফেজের সংখ্যাটি সাধারণভাবে কমে গিয়ে \(O(\sqrt{E})\) তে গিয়ে নামে এবং বাইপার্টাইট গ্রাফের (bipartite graphs) ক্ষেত্রে সেটি \(O(\sqrt{V})\)-এ নেমে আসে। তাই সর্বমোট কমপ্লেক্সিটি (complexity): \(O(E\sqrt{V})\) — হপক্রফ্ট-কার্প (Hopcroft-Karp) ম্যাচিং অ্যালগরিদমও (matching algorithm) একদম ঠিক একই বাউন্ড বা সীমায় অর্জিত হয়ে থাকে (যা মূলত বাইপার্টাইট গ্রাফে বা bipartite graphs এ ডিনিকের প্রয়োগ বা অ্যাপ্লাই করা ছাড়া আর কিছুই নয়)।

দ্রষ্টব্য: লেভেল গ্রাফটি (level graph) শুধুমাত্র দক্ষতার (efficiency) জন্য নয় — বরং এটি মূলত সঠিকতা বা কারেক্টনেসের (correctness) একটি টুল বা হাতিয়ার। DFS-কে শুধুমাত্র লেভেল-অ্যাডভান্সিং (level-advancing) বা সামনের দিকে এগিয়ে যাওয়া এজগুলোর (edges) মধ্যে সীমাবদ্ধ রাখার মাধ্যমে, ডিনিকের (Dinic's) অ্যালগরিদম এটি গ্যারান্টি দেয় যে এটি এই পর্যায়ে বা ফেজে প্রয়োজনের চেয়ে দীর্ঘতর পাথে বা পথে (paths) তার কোনো সময় নষ্ট করবে না।

ডিনিকের অ্যালগরিদম (Dinic's Algorithm)

from collections import deque


class Dinic:
    def __init__(self, n):
        self.n   = n
        self.adj = [[] for _ in range(n)]  # [to, rev_idx, cap]


    def add_edge(self, u, v, cap):
        self.adj[u].append([v, len(self.adj[v]), cap])
        self.adj[v].append([u, len(self.adj[u])-1, 0])  # backward edge


    def bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v, _, cap in self.adj[u]:
                if cap > 0 and self.level[v] < 0:
                    self.level[v] = self.level[u] + 1
                    q.append(v)
        return self.level[t] >= 0


    def dfs(self, u, t, pushed):
        if u == t: return pushed
        while self.it[u] < len(self.adj[u]):
            v, rev, cap = self.adj[u][self.it[u]]
            if cap > 0 and self.level[v] == self.level[u] + 1:
                d = self.dfs(v, t, min(pushed, cap))
                if d > 0:
                    self.adj[u][self.it[u]][2] -= d
                    self.adj[v][rev][2]         += d
                    return d
            self.it[u] += 1
        return 0


    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            self.it = [0] * self.n
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0: break
                flow += f
        return flow


d = Dinic(6)
d.add_edge(0,1,10); d.add_edge(0,2,10)
d.add_edge(1,3,5);  d.add_edge(2,4,10)
d.add_edge(3,5,10); d.add_edge(4,5,10)
d.add_edge(1,4,5)
print(d.max_flow(0, 5))  # 15
Output
15

Complexity

🌐 সাধারণ গ্রাফগুলো (General graphs)
\(O(V)\) ফেইজ বা পর্যায় (phases) × \(O(VE)\) ব্লকিং ফ্লো (blocking flow); অর্থাৎ স্পার্স গ্রাফের ক্ষেত্রে এটি \(O(VE^2)\) কে হারিয়ে দেয়
স্পার্স গ্রাফে বা পাতলা গ্রাফে (sparse graphs) এডমন্ডস-কার্পের (Edmonds-Karp) থেকে এটি অনেক ভালো কাজ করে \(O(V^2E)\)
⚡ ইউনিট ক্যাপাসিটি নেটওয়ার্ক বা ইউনিট ক্ষমতার নেটওয়ার্ক (Unit capacity networks)
পাথ বা পথের দৈর্ঘ্যগুলো খুব দ্রুতগামীতে বৃদ্ধি পায়; বাইপার্টাইট (bipartite) এবং ইউনিট গ্রাফের (unit graphs) ক্ষেত্রে শুধুমাত্র \(O(\sqrt{V})\) সংখ্যক পর্যায়গুলো বা ফেইজগুলোরই প্রয়োজন হয়
নিয়ার-লিনিয়ার পর্যায়গুলো বা ফেইজগুলো (Near-linear phases) \(O(E\sqrt{V})\)
👥 বাইপার্টাইট ম্যাচিং (Bipartite matching)
একটি ইউনিট-ক্যাপাসিটি বাইপার্টাইট ফ্লো নেটওয়ার্কের (unit-capacity bipartite flow network) ক্ষেত্রে ডিনিকের অ্যালগরিদম ঠিক হপক্রফ্ট-কার্পের (Hopcroft-Karp) সীমার বা বাউন্ডের সাথে বেশ হুবহু মিলে যায়
হপক্রফ্ট-কার্পের (Hopcroft-Karp) মতোই একই রকম \(O(E\sqrt{V})\)
🔍 ব্লকিং ফ্লো-র প্রতিটি পর্যায় বা ফেইজ (Each blocking flow phase)
প্রতিটি এজ বা প্রান্তকে প্রতি ফেইজ বা পর্যায়ে সর্বাধিক একবার মুছে ফেলা বা ডিলিট করা হয়; ডেড-এন্ড বা মৃত ভার্টেক্সগুলিকে (vertices) \(O(1)\) অ্যামর্টাইজড (amortized) সময়ে ছেঁটে ফেলা বা প্রুনড (pruned) করা হয়
ডেড-এন্ড প্রুনিং (dead-end pruning) এর কারণে লিনিয়ার (Linear) \(O(VE)\)

ছোট কুইজ

ডিনিকের অ্যালগরিদমে (Dinic's algorithm) লেভেল গ্রাফ (level graph) জিনিসটা মূলত কী?

পড়া চালিয়ে যান

এডমন্ডস-কার্প (Edmonds-Karp)
BFS সহকারে ফোর্ড-ফুলকারসন (Ford-Fulkerson) — গ্যারান্টিযুক্ত পলিনোমিয়াল টাইম বা বহুপদী সময় (polynomial time), যেখানে কোনো অসীম চক্র বা ইনফিনিট লুপ (infinite loops) থাকে না
→
ম্যাক্স ফ্লো / মিন কাট (Max Flow / Min Cut)
আপনার পাইপের নেটওয়ার্ক দিয়ে কতটুকু পানি যেতে পারবে? সেটির সিদ্ধান্ত নেবে বটলনেক (bottleneck) বা সরু পথটি
→
বাইপার্টাইট ম্যাচিং (Bipartite Matching)
ইন্টার্নশিপগুলোর সাথে শিক্ষার্থীদের মেলান — সুখী জুটির সর্বোচ্চ সংখ্যা খুঁজে বের করুন
→