ডায়াক্সট্রা(Dijkstra):

Dijkstra is a shortest path finding algorithm like BFS. BFS works only when the graph is unweighted.But if the graph is weighted, BFS doesn't work correctly. If the edges of a graph is non-negative and weighted, shortest path of the graph can be found by Dijkstra algorithm.

Motivating Problem:Given a weighted graph G and a starting source vertex s,what are the shortest paths from s to the other vertices of G?


Before knowing the details about Dijkstra algorithm, you need to know about path relaxation.
Relaxation: Suppose,there is  a place named Chawlkbazar where you want to go. Somehow(say,CUET->Oxyzen->GEC->New market->Chawlkbazar) you can reach Chawlkbazar from CUET by 30 minutes i.e distance[Chawlkbazar]=30.Now imagine a place named Bohaddorhat, which can be reached from CUET by 10 minutes i.e distance[Bohaddorhat]=10.Suppose, Chawlkbazar can be reached by 5 minutes from Bohaddorhat.Then we can see:

   distance[Bohaddorhat]+(time to reach from Bohaddorhat to Chawlkbazar)<distance[Chawlkbazar]

So,we can reset the cost for Chawlkbazar as:
   distance[Chawlkbazar]=distance[Bohaddorhat]+time to reach from Bohaddorhat to Chawlkbazar
This is the concept of path relaxation.If you have understood this,you have learned Dijkstra(almost😉)

Implementation: This is a greedy algorithm. It maintains a set S vertices whose final shortest path weights from source s have already been determined. The algorithm repeatedly selects a vertex u with estimated minimum cost and relaxes it. This can be implemented in many ways. Here,we'll use priority_queue.

Algorithm:
    1. Initially,
        (i) Set the distance to all vertices to be inf (a large number).
        (ii) Set distance[source]=0.

    2. Repeat the following process from source to vertex.
        (i) From the current vertex u(with minimum distance),relax all the neighbors of u. Relax(u,v).
        (ii) Set distance[v]=min(distance[v],distance[u]+cost(u,v)).

    3. Vertex u is now done and will not be visited again.Now,we'll greedily replace u with a unvisited
         vertex x with minimum distance distance[x].

Complexity: Dijkstra Algorithm's running time resembles both BFS and Prim's Algorithm for computing minimum spanning trees(O(log(V+E))). But here, O(log V) complexity will be added to sort the priority_queue every time. So, the overall complexity will be O(V log V+E).

References: 
    1. Introduction to Algorithm by Thomas H. Cormen.
    2. Competitive Programming by Steven & Felix Halim.
    3. Shafayet's Blog

Sample Code: Here is the sample code of dijkstra with path printing.

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	#define inf 100000000000000
	#define sz 123456
	#define pii pair<int,int>
	vector<pii>v[sz];
	vector<ll>dist(sz,inf);
	map<ll,ll>parent;
	void dijkstra(ll s){
	priority_queue<pii, vector<pii>, greater<pii> >pq;
	pq.push(make_pair(0,s));
	dist[s]=0;
	while(!pq.empty()){
	pii top=pq.top(); pq.pop();
	ll d=top.first; ll u=top.second;
	for(auto it:v[u]){
	ll v=it.first; int weight_u_v=it.second;
	if(dist[u]+weight_u_v<dist[v]){
	dist[v]=dist[u]+weight_u_v;
	parent[v]=u;
	pq.push(make_pair(dist[v],v));
	}
	}
	}
	}
	int main()
	{
	ll N,E,s,t,i,j,x,y,w;
	scanf("%lld%lld",&N,&E);
	for(i=0;i<E;i++){
	scanf("%lld%lld%lld",&x,&y,&w);
	v[x].push_back(make_pair(y,w));
	v[y].push_back(make_pair(x,w));
	}
	dijkstra(1);
	if(dist[N]==inf){printf("-1\n");return 0;}
	vector<ll>path;
	ll r=N;
	while(true){
	if(parent[r]==1){path.push_back(r);break;}
	path.push_back(r);
	r=parent[r];
	}
	path.push_back(1);
	reverse(path.begin(),path.end());
	for(auto it:path){
	printf("%lld ",it);
	}
	printf("\n");
	return 0;
	}

view raw Dijkstra.cpp hosted with ❤ by GitHub

Related Problems and solutions:
    1. LightOj 1002 - Country Roads
        Solution Idea: pretty straightforward.just try to figure out the meaning of this line "The cost is defined by the cost of the maximum road you have used to go to my city.".That means the shortest path will be the one where maximum cost(among one/more than one costs) is minimum.
        Solution: https://ideone.com/UYLvoi (See at your own risk👎)

    2. LightOj 1019 - Brush (V)
        Solution Idea: Direct implementation of Dijkstra algorithm.
        Solution: https://ideone.com/gSyCyh (See at your own risk👎)

    3. LightOj 1174 - Commandos
        Solution Idea: Nothing but just run dijkstra twice.Once to spread from the source and another to get together.Then the sum of the maximum will be answer.
        Solution: https://ideone.com/ZnPqLk (See at your own risk👎)