মডিউল ৭_৫ঃ ডিটেক্ট নেগেটিভ সাইকেল

আমরা এখন কিভাবে একটি গ্রাফ থেকে নেগেটিভ সাইকেল খুঁজে বের করা যায় সেটা দেখবো। কাজটি একদম সহজ একটি ছোট অবজারবেশন এর মাধ্যমেই।

প্রথমে একটু দেখে নেই নেগেটিভ সাইকেল কি?

এই গ্রাফটিতে যদি খেয়াল করি তাহলে দেখতে পাব প্রতিবার 0->1->2->0 তে আসতে সোর্স এর ডিস্টেন্স প্রতিবার কমতে থাকবে। আর সোর্স ডিস্টেন্স কমা মানে বাকি নোড গুলোর ও ডিস্টেন্স কমতে থাকবে। তাহলে এটি একটি ইনফাইনাইট লুপ হবে। এজন্য নেগেটিভ সাইকেলের কোনো ভ্যালিড আন্সার হয় না। আমরা শুধু ডিটেক্ট করতে পারি যে এখানে নেগেটিভ সাইকেল বিদ্যমান।

এখন কথা হচ্ছে সেটি কিভাবে করব। আমরা জানি Bellmanford এলগোরিদমে নোড-১ সংখ্যক বার যদি এজ লিস্টকে রিল্যাক্স করলে সকল নোড এর সোর্স থেকে শর্টেস্ট পাথ পাওয়া সম্ভব। তার মানে আমরা এও বলতে পারি যে যদি কোনো গ্রাফ এর এজ লিস্টকে Node-1 সংখ্যক বার রিল্যাক্স করার পর ও সে যদি আবার রিল্যাক্স হয় তাহলে সেখানে নেগেটিভ সাইকেল আছে। এই লজিক এর উপর বেইস করে আমরা নেগেটিভ সাইকেল খুঁজে বের করতে পারি।

কোডটি যদি দেখিঃ

// Some code
    for (int i = 1; i <= n - 1; i++)
    {
        for (Edge ed : EdgeList)
        {
            int u, v, c;
            u = ed.u;
            v = ed.v;
            c = ed.c;
            if (dis[u] < INT_MAX && dis[u] + c < dis[v])
            {
                dis[v] = dis[u] + c;
            }
        }
    }
    bool cycle = false;
    for (Edge ed : EdgeList)
    {
        int u, v, c;
        u = ed.u;
        v = ed.v;
        c = ed.c;
        if (dis[u] < INT_MAX && dis[u] + c < dis[v])
        {
            cycle = true;
            break;
        }
    }
    if (cycle)
    {
        cout << "Cycle found. No answer" << endl;
    }

এখানে শুধু চেক করেছি যে N-1 সংখ্যক বার রিল্যাক্স হওয়ার পর ও এজ লিস্ট আবার রিল্যাক্স হয়েছে কিনা। যদি হয় তাহলে cycle নামক বুলিয়ান ভেরিয়েবলটিকে true করে break করে দিলাম। যদি cycle true হয় তাহলে Cycle found প্রিন্ট করলাম আর নাহলে ডিস্টেন্স গুলো প্রিন্ট করলাম।

সম্পূর্ণ কোডঃ

// Some code
#include <bits/stdc++.h>
using namespace std;
class Edge
{
public:
    int u, v, c;
    Edge(int u, int v, int c)
    {
        this->u = u;
        this->v = v;
        this->c = c;
    }
};
const int N = 1e5 + 5;
int dis[N];
int main()
{
    int n, e;
    cin >> n >> e;
    vector<Edge> EdgeList;
    while (e--)
    {
        int u, v, c;
        cin >> u >> v >> c;
        EdgeList.push_back(Edge(u, v, c));
    }
    for (int i = 0; i < n; i++)
    {
        dis[i] = INT_MAX;
    }
    dis[0] = 0;
    for (int i = 1; i <= n - 1; i++)
    {
        for (Edge ed : EdgeList)
        {
            int u, v, c;
            u = ed.u;
            v = ed.v;
            c = ed.c;
            if (dis[u] < INT_MAX && dis[u] + c < dis[v])
            {
                dis[v] = dis[u] + c;
            }
        }
    }
    bool cycle = false;
    for (Edge ed : EdgeList)
    {
        int u, v, c;
        u = ed.u;
        v = ed.v;
        c = ed.c;
        if (dis[u] < INT_MAX && dis[u] + c < dis[v])
        {
            cycle = true;
            break;
        }
    }
    if (cycle)
    {
        cout << "Cycle found. No answer" << endl;
    }
    else
    {
        for (int i = 0; i < n; i++)
            cout << i << " -> " << dis[i] << endl;
    }
    return 0;
}