মডিউল ৬_৪ঃ Dijkstra Naive Approach Code

এখানে আমরা Dijkstra এর Naive ভারশন এর কোডটা দেখবোঃ

// Some code
```cpp
    int n, e;
    cin >> n >> e;
    while (e--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
```

এখানে গ্রাফটি বিল্ড করলাম।

// Some code
```cpp
    for (int i = 0; i < n; i++)
    {
        dis[i] = INT_MAX;
    }
```

ডিস্টেন্স এ্যারেকে ইনিশিয়ালি INT_MAX সেট করে রাখলাম যা infinity কে নির্দেশ করে।

// Some code
```cpp
void dijkstra(int src)
{
    queue<pair<int, int>> q;
    q.push({src, 0});
    dis[src] = 0;
    while (!q.empty())
    {
        pair<int, int> parent = q.front();
        q.pop();
        int node = parent.first;
        int cost = parent.second;
        for (pair<int, int> child : v[node])
        {
            int childNode = child.first;
            int childCost = child.second;
            if (cost + childCost < dis[childNode])
            {
                // path relax
                dis[childNode] = cost + childCost;
                q.push({childNode, dis[childNode]});
            }
        }
    }
}
```

এবার হলো মেইন কাজ। এখানে Dijkstra ফাংশন্টা বিল্ড করলাম।

// Some code
            if (cost + childCost < dis[childNode])
            {
                // path relax
                dis[childNode] = cost + childCost;
                q.push({childNode, dis[childNode]});
            }

এখানে এজ রিল্যাক্স এর কন্ডিশন সত্যি হলে নতুন ডিস্টেন্স সেট করে সেটাকে কিউতে পুশ করে দিচ্ছি।

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

// Some code
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
vector<pair<int, int>> v[N];
int dis[N];
void dijkstra(int src)
{
    queue<pair<int, int>> q;
    q.push({src, 0});
    dis[src] = 0;
    while (!q.empty())
    {
        pair<int, int> parent = q.front();
        q.pop();
        int node = parent.first;
        int cost = parent.second;
        for (pair<int, int> child : v[node])
        {
            int childNode = child.first;
            int childCost = child.second;
            if (cost + childCost < dis[childNode])
            {
                // path relax
                dis[childNode] = cost + childCost;
                q.push({childNode, dis[childNode]});
            }
        }
    }
}
int main()
{
    int n, e;
    cin >> n >> e;
    while (e--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    for (int i = 0; i < n; i++)
    {
        dis[i] = INT_MAX;
    }
    dijkstra(0);
    for (int i = 0; i < n; i++)
    {
        cout << i << "-> " << dis[i] << endl;
    }
    return 0;
}
```