> For the complete documentation index, see [llms.txt](https://phitron.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://phitron.gitbook.io/algorithm/undefined-1/_-dijkstra-path-printing.md). # মডিউল ১৪\_৪ঃ 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 কে কল করেছি। ```cpp 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 এর মাধ্যমে মনে রাখছি। ```cpp void dijkstra(ll s) { priority_queue, 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 করতেছি। ```cpp if (dis[n] == 1e18) cout << -1 << endl; else { ll x = n; vector 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;
}