18.Dijkstra'sAlgorithm.md

Dijkstra's Algorithm ( to find the minimum distance between source and all the nodes)

Adjacency list:

Though process: We'll use greedy to find the shortest path

Steps:

• Create a priority queue of min heap so that the one having the shortest distance would be in front
• Create a dist array and initialize it with infinity and assign the dist[src] = 0
• Now push the source into the priority queue
• Run until queue will not become empty
• Pop out the front element and traverse for all adjacent nodes, if any of them is eligible to update then update dist array and push that node along with its distance from source into the priority queue

Imp Note:

While doing this whole thing, you'll find out that sometime you'll have same distance in your priorrity queue more than once, so why we the same node with different distances is in the priority queue, the answer is that while doing this process whenever we'll find out a node having less dist than the already present in the dist array so we'll update it in our queue, but if at some point we'd find out that the same node is getting updated because we've found a path with less distance then the previous then we'll also update it in our queue, and the good thing is that, always that one would be used for the next process which has the least weight among all the pushed ones because this is priority queue and we're using greedy.

Here we can see that the node 5 is inserted two times, i.e (5, 5) and (7, 5) but only (5, 5) will be used from pri. queue because it has the shortest dist from source i.e 5 and the other one has distance 7. You can also ommit (7, 5), to do that you have to use set data structure instead of a priority queue i.e set<pair<int, int>> but deleletion doesn't will make much of a difference and priority queue is easier to implement

Time and Space complexity

• Time complexity would be O((N+E) + log n), O(N+E) for the traversing the adjacency list and logn for the priority queue
• Space complexity: Apart from the adjacency list we'd have O(N) + O(N), O(N) for the distance array and O(N) for the priority queue.

#include<bits/stdc++.h>
using namespace std;

void dijkstra(int v, int src, vector<pair<int, int>> adj[]){
	vector<int> dist(v, INT_MAX);
	//this priority queue is representing min heap
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int> > > pq;
	dist[src] = 0;
	//push the source in your priority queue
	pq.push(make_pair(0, src));
	//run until queue will not become empty
	while(!pq.empty()){
		//fetch the top node from the priority queue
		//top element of the priority queue will have least weight
		int node = pq.top().second;
		int wt = pq.top().first;
		pq.pop();
		//compare the distance, if distance can be updated then update it and push it in priority queue
		for(auto it : adj[node]){
			if(dist[node] + it.second < dist[it.first]){
				dist[it.first] = dist[node] + it.second;
				pq.push(make_pair(dist[it.first]), it.first);
			}
		}
	}

	cout<<"The distance from source to all vertices would be :";
	for(int i=0; i<v; i++)
		cout<<dist[i]<<" ";
	cout<<endl;
}
int main(){
	cout<<"Enter the number of vertices and no. of nodes: ";
	int n, m, src;
	cin>>n>>m;

	//this is  undirected weighted graph
	cout<<"Enter all the edges, i.e, start and end of node and their weight: "<<endl;
	vector<pair<int, int>> adj[n];
	for(int i=0; i<m; i++){
		int u, v, wt;
		cin>>u>>v>>wt;
		adj[u].push_back(make_pair(v, wt));
		adj[v].push_back(make_pair(u, wt));
	}
	cout<<"Enter the source of the graph: ";
	cin>>src;
	dijkstra(n, src, adj);
	return 0;
}

OUTPUT: