গ্রাফে নেগেটিভ সাইকেল খুঁজে বের করা#
আপনাকে $N$টি ভার্টেক্স এবং $M$টি এজবিশিষ্ট একটি ডিরেক্টেড ওয়েটেড গ্রাফ $G$ দেওয়া হয়েছে। এতে নেগেটিভ ওয়েটের যেকোনো সাইকেল খুঁজে বের করুন, যদি এই ধরনের সাইকেল বিদ্যমান থাকে।
সমস্যাটির আরেকটি রূপে আপনাকে এমন সমস্ত ভার্টেক্স জোড়া খুঁজে বের করতে হবে যাদের মধ্যে ইচ্ছামতো ছোট ওয়েটের পাথ আছে।
এই সমস্যার দুটি প্রকরণ সমাধানের জন্য ভিন্ন ভিন্ন অ্যালগরিদম ব্যবহার করা সুবিধাজনক, তাই আমরা এখানে উভয়ই আলোচনা করব।
বেলম্যান-ফোর্ড অ্যালগরিদম ব্যবহার#
বেলম্যান-ফোর্ড অ্যালগরিদম আপনাকে গ্রাফে নেগেটিভ ওয়েটের সাইকেল আছে কি না পরীক্ষা করতে দেয়, এবং থাকলে এই ধরনের একটি সাইকেল খুঁজে বের করতে দেয়।
অ্যালগরিদমের বিস্তারিত বেলম্যান-ফোর্ড অ্যালগরিদমের আর্টিকেলে বর্ণিত আছে। এখানে আমরা শুধু এই সমস্যায় এর প্রয়োগ বর্ণনা করব।
বেলম্যান-ফোর্ডের স্ট্যান্ডার্ড ইমপ্লিমেন্টেশন কোনো শুরুর ভার্টেক্স $v$ থেকে পৌঁছানো যায় এমন নেগেটিভ সাইকেল খোঁজে; তবে, অ্যালগরিদমটি পরিবর্তন করা যায় যাতে গ্রাফে যেকোনো নেগেটিভ সাইকেল খুঁজে পায়। এর জন্য আমাদের সমস্ত দূরত্ব $d[i]$ শূন্যে সেট করতে হবে, অসীমে নয় — যেন আমরা সমস্ত ভার্টেক্স থেকে একসাথে শর্টেস্ট পাথ খুঁজছি; নেগেটিভ সাইকেল সনাক্তকরণের বৈধতা এতে প্রভাবিত হয় না।
বেলম্যান-ফোর্ড অ্যালগরিদমের $N$টি ইটারেশন করুন। শেষ ইটারেশনে কোনো পরিবর্তন না হলে, গ্রাফে নেগেটিভ ওয়েটের সাইকেল নেই। অন্যথায় যে ভার্টেক্সের দূরত্ব পরিবর্তন হয়েছে সেটি নিন, এবং এটি থেকে তার পূর্বপুরুষদের মধ্য দিয়ে যান যতক্ষণ না একটি সাইকেল পাওয়া যায়। এই সাইকেলটিই কাঙ্ক্ষিত নেগেটিভ ওয়েটের সাইকেল হবে।
ইমপ্লিমেন্টেশন#
struct Edge {
int a, b, cost;
};
int n;
vector<Edge> edges;
const int INF = 1000000000;
void solve() {
vector<int> d(n, 0);
vector<int> p(n, -1);
int x;
for (int i = 0; i < n; ++i) {
x = -1;
for (Edge e : edges) {
if (d[e.a] + e.cost < d[e.b]) {
d[e.b] = max(-INF, d[e.a] + e.cost);
p[e.b] = e.a;
x = e.b;
}
}
}
if (x == -1) {
cout << "No negative cycle found.";
} else {
for (int i = 0; i < n; ++i)
x = p[x];
vector<int> cycle;
for (int v = x;; v = p[v]) {
cycle.push_back(v);
if (v == x && cycle.size() > 1)
break;
}
reverse(cycle.begin(), cycle.end());
cout << "Negative cycle: ";
for (int v : cycle)
cout << v << ' ';
cout << endl;
}
}ফ্লয়েড-ওয়ারশাল অ্যালগরিদম ব্যবহার#
ফ্লয়েড-ওয়ারশাল অ্যালগরিদম সমস্যার দ্বিতীয় প্রকরণ সমাধান করতে দেয় - এমন সমস্ত ভার্টেক্স জোড়া $(i, j)$ খুঁজে বের করা যাদের মধ্যে শর্টেস্ট পাথ নেই (অর্থাৎ ইচ্ছামতো ছোট ওয়েটের পাথ বিদ্যমান)।
বিস্তারিত আবারও ফ্লয়েড-ওয়ারশাল আর্টিকেলে পাওয়া যাবে, এবং এখানে আমরা শুধু এই সমস্যায় এর প্রয়োগ বর্ণনা করি।
গ্রাফে ফ্লয়েড-ওয়ারশাল অ্যালগরিদম চালান। প্রাথমিকভাবে প্রতিটি $v$-এর জন্য $d[v][v] = 0$। কিন্তু অ্যালগরিদম চালানোর পরে $d[v][v]$ $0$-এর চেয়ে ছোট হবে যদি $v$ থেকে $v$-তে নেগেটিভ দৈর্ঘ্যের পাথ থাকে। আমরা এটি ব্যবহার করে এমন সমস্ত ভার্টেক্স জোড়াও খুঁজে বের করতে পারি যাদের মধ্যে শর্টেস্ট পাথ নেই। আমরা সমস্ত ভার্টেক্স জোড়া $(i, j)$-এর উপর ইটারেট করি এবং প্রতিটি জোড়ার জন্য পরীক্ষা করি তাদের মধ্যে শর্টেস্ট পাথ আছে কি না। এটি করতে একটি মধ্যবর্তী ভার্টেক্স $t$-এর সমস্ত সম্ভাবনা চেষ্টা করি। $(i, j)$-এর মধ্যে শর্টেস্ট পাথ নেই, যদি মধ্যবর্তী ভার্টেক্সগুলোর কোনো একটি $t$-এর জন্য $d[t][t] < 0$ হয় (অর্থাৎ $t$ নেগেটিভ ওয়েটের সাইকেলের অংশ), $i$ থেকে $t$-এ পৌঁছানো যায় এবং $t$ থেকে $j$-এ পৌঁছানো যায়। তাহলে $i$ থেকে $j$-এর পাথ ইচ্ছামতো ছোট ওয়েটের হতে পারে। আমরা এটিকে -INF দিয়ে চিহ্নিত করব।
ইমপ্লিমেন্টেশন#
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int t = 0; t < n; ++t) {
if (d[i][t] < INF && d[t][t] < 0 && d[t][j] < INF)
d[i][j] = - INF;
}
}
}