Dijkstra algorithm

Dijkstra’s algorithm is also an algorithm to solve the shortest path problem of a single source. His algorithm takes advantage of greedy ideas and cannot have negative edge weights.

Algorithm steps

  1. Firstly, all nodes connected with the starting point S are put into the set, and the node u with the smallest distance is found. Then u is the first node to determine the shortest path. The path from S to U must be the shortest, because S must be farther to u by going somewhere else.
  2. And then I’m going to take the node u, which is the shortest distance from s in the set, and I’m going to put the node connected to u into the set.
  3. Continuing with the above operations, the shortest path of a node can be determined during each iteration.

Algorithm analysis

  1. Graph storage problem: use chain forward star storage to prevent the graph space is too large.

  2. How to quickly find the node with the smallest distance in the set in each iteration: The top element of each heap is the smallest node in the set. Here, I use priority_queue<> in STL of C++. Remember that if the smallest node is found, the current node must be marked as the shortest distance and no further access is required.

  3. Time complexity: O(mlog2(n))

code

typedef pair<int.int> PII;// Is equivalent to a structure: first indicates the shortest distance, second indicates the node number
int d[N];
int e[N],ne[N],w[N],idx;// The weight of the edge at position I (e[I]) that points to the node ne[I] that points to position I (w[I])
int h[N];//h[u] represents the position of the first edge connected to node u
int b;/ / starting point
bool vis[N];// Indicates whether the shortest path of node I has been found.
void init(a)
{
    memset(d,0x3f.sizeof d);// initialize the initial distance is infinite
	memset(h,- 1.sizeof h);// initialize h to position -1
}
void add(int a,int b,int c)// Add edges and nodes to the graph
{
	e[idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
}
void Dijkstra(a) 
{
	priority_queue<PII,vector<PII>,greater<PII> > heap;
	heap.push({0,b});
	d[b]=0;
	while(! heap.empty())
	{
		auto t=heap.top(a); heap.pop(a);// Select the node with the smallest distance from the set and delete it
		int from=t.second,mind=t.first;
		if(vis[from]) continue;// If it is used, it is not used
		vis[from]=1;// set the node from already used
		for(inti=h[from]; ~i; i=ne[i])// Iterate over the edge starting from
		{
			int to=e[i];
			if(d[to]>d[from]+w[i])
			{
				d[to]=d[from]+w[i];
				heap.push({d[to],to}); }}}}Copy the code