Problem 23-Dijkstra's Algorithm - Using Priority Queue - C++

         

Dijkstra's Algorithm - Using Priority Queue - C++

by Ujjal Roy

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

vector<pair<ll,ll>>grp[100];

ll dis[100];

void  dijkstra(ll node)

{

    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>pq;

    pq.push({0,node});

    dis[node]=0;

    while(!pq.empty())

    {

        ll dist=pq.top().first;

        ll nod=pq.top().second;

        pq.pop();

        for(ll i=0;i<grp[nod].size();i++)

        {

            ll adjDist=grp[nod][i].second;

            ll adjNode=grp[nod][i].first;

            if((adjDist+dist)<dis[adjNode])

            {

                dis[adjNode]=adjDist+dist;

                pq.push({dis[adjNode],adjNode});

            }

        }

    }

}

int main()

{

    ll n,m,i;

    cin>>n>>m;

    while(m--)

    {

        ll u,v,w;

        cin>>u>>v>>w;

        grp[u].push_back({v,w});

        grp[v].push_back({u,w});

    }

    for(i=0;i<n;i++)

    {

       dis[i]=100000000;

    }

    //dis[0]=0;

    dijkstra(0);

    for(i=0;i<n;i++)cout<<dis[i]<<" ";

    return 0;

}