/* IMP:- if the graph is umweighted use simple BFS to find the min distance. -> to find the single source min distance from source vertex to all other vertices Dijkstra algorithm. Steps:- ->just like the simple bfs just change the queue to small priority queue. 1)create the dist array which contain the dist of each node from source vertex 2)now make dist[source] = 0 && initiliaze a small priority queue of pair 3)push the pair of (0,source) into priority queue 4)run a loop till pq.size>0 ->get the currdist = pq.top().first && curr = pq.top().second && pop from queue -> if(visi[curr]) continue; -> else ->make visi[curr] = true ->dist[curr] = currdist ->iterate over the adjacency list of curr ->if visi[child] is false ->push the pair of weight_of_child+currdist && child into the priority queue 5)at last the dist array will contain the minimum distance of each node from source node. */ void dijkstra(ll s, ll n) { vector<ll> dist(n + 1); dist[s] = 0; priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; pq.push({0, s}); while (pq.size() > 0) { int currdist = pq.top().first; int curr = pq.top().second; pq.pop(); if (visi[curr]) continue; visi[curr] = true; dist[curr] = currdist; for (auto itr : g[curr]) { if (visi[itr.first] == false) { pq.push({itr.second + currdist, itr.first}); } } } for (int i = 0; i < n; i++) cout << i << " " << dist[i] << endl; }