মডিউল ৭_৮ঃ Floyd Warshall Algoritm Code

আমরা এখন Floyd Warshall Algorithm এর কোডটা দেখবো।

// Some code
    ll n, e;
    cin >> n >> e;
    ll adj[n][n];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            adj[i][j] = INT_MAX;
            if (i == j)
                adj[i][j] = 0;
        }
    }

এখানে গ্রাফের এডজেসেন্সি ম্যাট্রিক্সটা ইনিশিয়ালাইজ করলাম।

// Some code
    while (e--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a][b] = c;
    }

এবার এজ ইনপুট নিয়ে সেটার ভ্যালু এডজেসেন্সি ম্যাট্রিক্স এ রাখলাম।

// Some code
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (adj[i][k] + adj[k][j] < adj[i][j])
                {
                    adj[i][j] = adj[i][k] + adj[k][j];
                }
            }
        }
    }

এখন আসল কাজটা করব। এখানে k এর লুপটা সেই মধ্যস্ততাকারী নোডকে চুজ করবে। আর i আর j লুপ যথাক্রমে সোর্স আর ডেস্টিনেশন হিসেবে কাজ করবে। আর রিল্যাক্স এর লজিকটা হচ্ছে যদি i->k + k->j < i->j হয় তাহলে তা আপডেট হবে।

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

// Some code
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
    ll n, e;
    cin >> n >> e;
    ll adj[n][n];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            adj[i][j] = INT_MAX;
            if (i == j)
                adj[i][j] = 0;
        }
    }
    while (e--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a][b] = c;
    }
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (adj[i][k] + adj[k][j] < adj[i][j])
                {
                    adj[i][j] = adj[i][k] + adj[k][j];
                }
            }
        }
    }
    // cout << "AFTER" << endl;
    // for (int i = 0; i < n; i++)
    // {
    //     for (int j = 0; j < n; j++)
    //     {
    //         if (adj[i][j] == INT_MAX)
    //             cout << "INF ";
    //         else
    //             cout << adj[i][j] << " ";
    //     }
    //     cout << endl;
    // }

    for (int i = 0; i < n; i++)
    {
        if (adj[i][i] < 0)
        {
            cout << "Cycle detected" << endl;
            break;
        }
    }
    return 0;
}