মডিউল ১৪_৪ঃ Dijkstra Path Printing

আপনাকে একটি weighted undirected graph দেওয়া হয়েছে। vertice গুলো 1 থেকে n পর্যন্ত গণনা করা হয়েছে। আপনার কাজ হল vertex1 এবং vertexn এর মধ্যে সবচেয়ে shortest পথটি খুঁজে বের করা।

সমাধানঃ

প্রথমে number of node এবং number of edge ইনপুট নিয়েছি, এরপর edge গুলোকে ইনপুট নিয়ে adjacency list বানিয়েছি undirected graph এর জন্য। এরপর dis এবং par array কে initialize করেছি, তারপর source = 1 পাঠিয়ে bfs কে কল করেছি।

ll n, e;
cin >> n >> e;
while (e--)
{
    ll a, b, c;
    cin >> a >> b >> c;
    v[a].push_back({b, c});
    v[b].push_back({a, c});
}
for (ll i = 1; i <= n; i++)
{
    dis[i] = 1e18;
    par[i] = -1;
}
dijkstra(1);

নরমালি bfs যেইভাবে bfs function লিখা হয় সেইভাবেই লিখেছি। এইখানে shortest path print করার জন্য কার parent কে সেইটিকে par array এর মাধ্যমে মনে রাখছি।

void dijkstra(ll s)
{
    priority_queue<pi, vector<pi>, cmp> pq;
    pq.push({s, 0});
    dis[s] = 0;
    while (!pq.empty())
    {
        pi parent = pq.top();
        pq.pop();
        ll parentNode = parent.first;
        ll parentCost = parent.second;
        for (pi child : v[parentNode])
        {
            ll childNode = child.first;
            ll childCost = child.second;
            if (parentCost + childCost < dis[childNode])
            {
                dis[childNode] = parentCost + childCost;
                pq.push({childNode, dis[childNode]});
                par[childNode] = parentNode;
            }
        }
    }
}

bfs function শেষ হহওয়ার পর , n নোডের distance চেক করছি, এবং যদি নোড 1 থেকে নোড n এ যাওয়া যায় তাহলে path print করতেছি।

if (dis[n] == 1e18)
        cout << -1 << endl;
else
{
    ll x = n;
    vector<ll> path;
    while (x != -1)
    {
        path.push_back(x);
        x = par[x];
    }
    reverse(path.begin(), path.end());
    for (ll val : path)
        cout << val << " ";
    cout << endl;
}

সম্পূর্ণ কোডটি

#include <bits/stdc++.h>
#define ll long long
#define pi pair<ll, ll>
using namespace std;
const ll N = 1e5 + 5;
vector<pi> v[N];
ll dis[N];
ll par[N];
class cmp
{
public:
    bool operator()(pi a, pi b)
    {
        return a.second > b.second;
    }
};
void dijkstra(ll s)
{
    priority_queue<pi, vector<pi>, cmp> pq;
    pq.push({s, 0});
    dis[s] = 0;
    while (!pq.empty())
    {
        pi parent = pq.top();
        pq.pop();
        ll parentNode = parent.first;
        ll parentCost = parent.second;
        for (pi child : v[parentNode])
        {
            ll childNode = child.first;
            ll childCost = child.second;
            if (parentCost + childCost < dis[childNode])
            {
                dis[childNode] = parentCost + childCost;
                pq.push({childNode, dis[childNode]});
                par[childNode] = parentNode;
            }
        }
    }
}
int main()
{
    ll n, e;
    cin >> n >> e;
    while (e--)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    for (ll i = 1; i <= n; i++)
    {
        dis[i] = 1e18;
        par[i] = -1;
    }
    dijkstra(1);
    if (dis[n] == 1e18)
        cout << -1 << endl;
    else
    {
        ll x = n;
        vector<ll> path;
        while (x != -1)
        {
            path.push_back(x);
            x = par[x];
        }
        reverse(path.begin(), path.end());
        for (ll val : path)
            cout << val << " ";
        cout << endl;
    }
    return 0;
}