ফোর্ড-ফুলকারসন অ্যালগরিদম ব্যবহার করা হয় একটি প্রদত্ত গ্রাফে শুরুর ভার্টেক্স (source) থেকে সিংক ভার্টেক্স (sink) পর্যন্ত ম্যাক্সিমাম ফ্লো শনাক্ত করতে। এই গ্রাফে, প্রতিটি এজের একটি ক্যাপাসিটি থাকে। দুটি ভার্টেক্স দেওয়া থাকে: Source এবং Sink। সোর্স ভার্টেক্সের সব এজ আউটওয়ার্ড, কোনো ইনওয়ার্ড নেই, এবং সিংকের সব এজ ইনওয়ার্ড, কোনো আউটওয়ার্ড নেই।
কিছু সীমাবদ্ধতা রয়েছে:
- একটি এজের ওপর ফ্লো সেই এজের দেওয়া ক্যাপাসিটি অতিক্রম করতে পারবে না।
- ইনকামিং ফ্লো এবং আউটগোইং ফ্লো প্রতিটি এজের জন্য সমান হবে, শুধু সোর্স এবং সিংক বাদে।
ইনপুট এবং আউটপুট
ইনপুট: অ্যাডজেসেন্সি ম্যাট্রিক্স: 0 10 0 10 0 0 0 0 4 2 8 0 0 0 0 0 0 10 0 0 0 0 9 0 0 0 6 0 0 10 0 0 0 0 0 0 আউটপুট: ম্যাক্সিমাম ফ্লো: 19
এলগরিদম
bfs(vert, start, sink)
ইনপুট: ভার্টেক্স লিস্ট, শুরুর নোড, এবং সিংক নোড।
আউটপুট: সিংক ভিজিটেড হলে true।
শুরু
প্রাথমিকভাবে সব নোডকে অনভিজিটেড চিহ্নিত করুন
start-এর স্টেটকে ভিজিটেড করুন
start নোডের প্রিডিসেসর হলো φ
start কে কিউ qu-তে ইনসার্ট করুন
যতক্ষণ qu খালি নয়, করুন
কিউ থেকে এলিমেন্ট ডিলিট করুন এবং u-তে সেট করুন
রেজিডুয়াল গ্রাফের সব ভার্টেক্স i এর জন্য, করুন
যদি u এবং i সংযুক্ত থাকে, এবং i অনভিজিটেড, তবে
ভার্টেক্স i কে কিউতে যোগ করুন
i-এর প্রিডিসেসর হলো u
i কে ভিজিটেড চিহ্নিত করুন
শর্ত শেষ
শেষ লুপ
শেষ লুপ
সিংক ভার্টেক্সের স্টেট ভিজিটেড হলে true ফেরত দিন
শেষ
fordFulkerson(vert, source, sink)
ইনপুট: ভার্টেক্স লিস্ট, সোর্স ভার্টেক্স, এবং সিংক ভার্টেক্স।
আউটপুট: সোর্স থেকে সিংক পর্যন্ত ম্যাক্সিমাম ফ্লো।
শুরু
একটি রেজিডুয়াল গ্রাফ তৈরি করুন এবং প্রদত্ত গ্রাফকে সেটিতে কপি করুন
যতক্ষণ bfs(vert, source, sink) true হয়, করুন
pathFlow := ∞
v := সিংক ভার্টেক্স
যতক্ষণ v ≠ শুরুর ভার্টেক্স, করুন
u := v-এর প্রিডিসেসর
pathFlow := pathFlow এবং residualGraph[u, v]-এর ন্যূনতম
v := v-এর প্রিডিসেসর
শেষ লুপ
v := সিংক ভার্টেক্স
যতক্ষণ v ≠ শুরুর ভার্টেক্স, করুন
u := v-এর প্রিডিসেসর
residualGraph[u,v] := residualGraph[u,v] - pathFlow
residualGraph[v,u] := residualGraph[v,u] - pathFlow
v := v-এর প্রিডিসেসর
শেষ লুপ
maxFlow := maxFlow + pathFlow
শেষ লুপ
return maxFlow
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <queue>
#define NODE 6
using namespace std;
typedef struct node {
int val;
int state; // স্ট্যাটাস
int pred; // প্রিডিসেসর
} node;
int minimum(int a, int b) {
return (a < b) ? a : b;
}
int resGraph[NODE][NODE];
int graph[NODE][NODE] = {
{0, 10, 0, 10, 0, 0},
{0, 0, 4, 2, 8, 0},
{0, 0, 0, 0, 0, 10},
{0, 0, 0, 0, 9, 0},
{0, 0, 6, 0, 0, 10},
{0, 0, 0, 0, 0, 0}
};
int bfs(node *vert, node start, node sink) {
node u;
int i, j;
queue<node> que;
for(i = 0; i < NODE; i++) {
vert[i].state = 0; // ভিজিটেড নয়
}
vert[start.val].state = 1; // ভিজিটেড
vert[start.val].pred = -1; // কোনো প্যারেন্ট নোড নেই
que.push(start); // শুরুর নোড ইনসার্ট করুন
while(!que.empty()) {
// কিউ থেকে ডিলিট করুন এবং প্রিন্ট করুন
u = que.front();
que.pop();
for(i = 0; i < NODE; i++) {
if(resGraph[u.val][i] > 0 && vert[i].state == 0) {
que.push(vert[i]);
vert[i].pred = u.val;
vert[i].state = 1;
}
}
}
return (vert[sink.val].state == 1);
}
int fordFulkerson(node *vert, node source, node sink) {
int maxFlow = 0;
int u, v;
for(int i = 0; i < NODE; i++) {
for(int j = 0; j < NODE; j++) {
resGraph[i][j] = graph[i][j]; // প্রাথমিকভাবে রেজিডুয়াল গ্রাফ হলো মূল গ্রাফ
}
}
while(bfs(vert, source, sink)) {
// বিএফএস অ্যালগরিদম দিয়ে অগমেন্টেড পথ খুঁজে বের করুন
int pathFlow = 999; // অনন্ত হিসেবে
for(v = sink.val; v != source.val; v = vert[v].pred) {
u = vert[v].pred;
pathFlow = minimum(pathFlow, resGraph[u][v]);
}
for(v = sink.val; v != source.val; v = vert[v].pred) {
u = vert[v].pred;
resGraph[u][v] -= pathFlow; // এজের রেজিডুয়াল ক্যাপাসিটি আপডেট করুন
resGraph[v][u] += pathFlow; // রিভার্স এজের রেজিডুয়াল ক্যাপাসিটি আপডেট করুন
}
maxFlow += pathFlow;
}
return maxFlow; // ওভারঅল ম্যাক্স ফ্লো
}
int main() {
node vertices[NODE];
node source, sink;
for(int i = 0; i < NODE; i++) {
vertices[i].val = i;
}
source.val = 0;
sink.val = 5;
int maxFlow = fordFulkerson(vertices, source, sink);
cout << "Maximum flow is: " << maxFlow << endl;
}
আউটপুট
Maximum flow is: 19
