মডিউল ৬_৭ঃ Dijkstra Optimize Code

এখন আমরা Dijkstra এলগোরিদম এর অপ্টিমাইজ ভার্সন এর কোডটা ইমপ্লিমেন্ট করব।

// 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});
    }
    for (int i = 0; i < n; i++)
    {
        dis[i] = INT_MAX;
    }
    dijkstra(0);
```

এখানে সব আগের ভার্শন এর মতোই।

// Some code
```cpp
class cmp
{
public:
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        return a.second > b.second;
    }
};
```

// Some code
```cpp
 priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
    pq.push({src, 0});
```

এখন আমরা প্রাইওরিটি কিউ এর মাধ্যমে নোড গুলোর ট্র্যাক রাখব ও যাতে সেই কিউ আমাদের সব সময় ছোট কস্ট এর নোড ফ্রন্ট হিসেবে দেয় তাই একটি কাস্টম কম্পেয়ার ক্লাস লিখলাম।

// Some code
```cpp
    while (!pq.empty())
    {
        pair<int, int> parent = pq.top();
        pq.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;
                pq.push({childNode, dis[childNode]});
            }
        }
    }
```

এখানে আমরা priority queue এম্পটি না হওয়া অব্দি লুপ চালাবো আর টপ ভ্যালুকে নিব। এবং পপ করে দিব। সেই নোড এর প্রত্যেক চাইল্ড এর কাছে যাবো আর যদি তাদেরকে রিল্যাক্স করা পসিবল হয় তাহলে তাদের রিল্যাক্স করে priority queue তে পুশ করে দিব।

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

// Some code
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
vector<pair<int, int>> v[N];
int dis[N];
class cmp
{
public:
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        return a.second > b.second;
    }
};
void dijkstra(int src)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
    pq.push({src, 0});
    dis[src] = 0;
    while (!pq.empty())
    {
        pair<int, int> parent = pq.top();
        pq.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;
                pq.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;
}
```