মডিউল ৭_৪ঃ Bellmanford Algorithm Code

আমরা Bellmanford algorithm এর থিওরি সম্পর্কে জেনে গেছি। এখন আমরা সেই থিওরিকে কোড এ কনভার্ট করব।

// Some code
class Edge
{
public:
    int u, v, c;
    Edge(int u, int v, int c)
    {
        this->u = u;
        this->v = v;
        this->c = c;
    }
};

এখানে আমরা এজলিস্ট এর জন্য প্রতিটি এজ এ কি কি এলিমেন্ট থাকবে সেটার জন্য একটি ক্লাস বানিয়েছি। প্রত্যেক এজ এর অবজেক্ট এ এজ এর শুরুর নোড থাকবে এজ এর শেষের নোড থাকবে আর একটি কস্ট থাকবে।

// Some code
    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;

উপরের অংশে আমরা এজলিস্টটি তৈরি করেছি। আর সব এর জন্য distance array তে ইনিশিয়ালি INT_MAX দিয়ে রেখেছি যা ইনফাইনাইটকে নির্দেশ করছে। শেষে সোর্স এর ডিস্টেন্স ০ করে নিচ্ছি।

    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;
            }
        }
    }

এখন আমরা আসল কাজটি করব। আমরা নোড-১ সংখ্যক বার এজ রিল্যাক্সেশন করব। এজ লিস্ট থেকে প্রতিটি এজকে বের করে নিচ্ছি। এরপর প্রথমে চেক করছি যে প্যারেন্ট নোড এর ডিস্টেনস যদি INT_MAX থেকে যায় তাহলে রিল্যাক্স যাতে না করে আর যদি কম হয় তাহলে যদি পাথ রিল্যাক্স এর কন্ডিশন ফুলফিল হয় তাহলে ডিস্টেন্স এ্যারেকে আপডেট করে দিব।

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

#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;
            }
        }
    }
    for (int i = 0; i < n; i++)
        cout << i << " -> " << dis[i] << endl;
    return 0;
}