Dijkstra Algorithm (single source shortest path)🚩🚩

/*
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;
}