Shortest path problem

For the algorithm operation of related concepts, see This article.
Only the codes of Dijkstra algorithm and Floyd algorithm are introduced here.

Dijkstra algorithm

BFS can find the shortest path length from a point to another point. Dijkstra algorithm is mainly to find the shortest path length from a point to all other points (you can do it slowly with BFS, and the time complexity will be very large).

Will the Dijkstra algorithm have a situation that the point of a certain path that has been out of the queue is not the shortest path? In fact, let's use the counter evidence method to think about it. If such a situation occurs, how can this point be the first to leave the team? So you can understand.

As for many blogs, the problem of rings in the path mentioned in the book does not exist in the Dijkstra algorithm with non negative edge weight, and the reason is obvious.

//Output the shortest path and shortest path length from the source point v to all other nodes. path[i] is the precursor node and dist is the shortest path length 
void Dispath(MatGraph g,int dist[],int path[],int S[],int v){int k;
	int apath[MAXV],d;					
	for (int i=0;i<g.n;i++)	if (S[i]==1&&i!=v){
		printf("  From vertex%d To vertex%d The path length of is:%d\t Path is:",v,i,dist[i]);//Print shortest path length 
		d=0; apath[d]=i; k=path[i];//d is the number of vertices in the shortest path, and apath stores the reverse path obtained by backtracking 
		if (k==-1) printf("no path\n");//k=path[i] is - 1, indicating that there is no determined shortest path 
		else{//Trace back from I to the starting point v through path[i], get the shortest path in reverse order, and store it in apath	
			while (k!=v){d++; apath[d]=k; k=path[k];}
				d++; apath[d]=v;//Add start point on path
				//Reverse print path 
				printf("%d",apath[d]); for (int j=d-1;j>=0;j--) printf(",%d",apath[j]);
				printf("\n");
			}
	}
}//Dijkstra algorithm, v is the source point, and S[i] indicates whether the shortest path from node v to node i has been determined
//dist[i] indicates the shortest path length from node v to node i when the algorithm runs. dist[i]=INF indicates that it cannot be reached 
//path[i] indicates the precursor node of node i under the current shortest path. It cannot be reached. Path value = - 1, no precursor node path value = 0 
void Dijkstra(MatGraph g,int v){int dist[MAXV],path[MAXV],S[MAXV];					
	int Mindis,u;
	//Starting from the source point, modify the dist and path of the adjacent point of the node currently being accessed 
	for (int i=0;i<g.n;i++){dist[i]=g.edges[v][i]; S[i]=0;					
		if (g.edges[v][i]<INF) path[i]=v; else path[i]=-1;			
	}S[v]=1; path[v]=0;//At first, only the shortest path to the source point is determined
	//Find the shortest path of the remaining n-1 points 
	for (int i=0;i<g.n-1;i++){Mindis=INF;
		//Find the node u with the shortest distance from the source point among the nodes whose shortest path is not determined, and determine its shortest path 
		for (int j=0;j<g.n;j++)	if (S[j]==0&&dist[j]<Mindis){u=j; Mindis=dist[j];}
		S[u]=1;//Modify the dist and path of the adjacency point of the node currently being accessed (the shortest path of the adjacency point is not determined)		
		for (int j=0;j<g.n;j++) if (S[j]==0) if (g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j]){	
			dist[j]=dist[u]+g.edges[u][j]; path[j]=u;
		}
	}Dispath(g,dist,path,S,v);//Output shortest path
}

As for optimization, you can use the priority queue to add the reachable points to the priority queue, and then take the head of the priority queue each time, and modify the dist value according to the endpoint of its edge. Due to the superiority of the priority queue as a container, the time complexity can be optimized. The optimized code is as follows:

//For the edge structure, from and to represent the start point and end point, dist represents the edge weight 
struct Edge{int from,to,dist;
	Edge(int u,int v,int d):from(u),to(v),dist(d){}
};//For the structure of nodes, d represents the d value of nodes, and u represents the number of nodes 
struct HeapNode{int d,u;//Constructs a sort method that increments by d value 
	bool operator < (const HeapNode& rhs) const{return d>rhs.d}
};//d[i] represents the distance from s to point I, and p[i] represents the path number to node i under the current (optimal) path 
struct Dijkstra{int n,m,d[maxn],p[maxn],v[maxn];//v[i] indicates whether point I is marked 
	vector<Edge>edges; vector<int>G[maxn];//G[i] represents all edges starting from I 
	void init(int n){this->n=n;//Initialize and empty all tables 
		for (int i=0;i<n;i++) G[i].clear(); edges.clear();
	}//Read in the edge list of digraph 
	void AddEdge(int from,int to,int dist){
		edges.push_back(Edge(from,to,dist));
		m=edges.size(); G[from].push_back(m-1);//m represents the number of edges		
	}//In the algorithm body, the Q queue stores nodes that have not been marked but whose d value is not INF
	//Because only unmarked nodes will be traversed 
	//And only if the d value is not INF can it have the meaning of comparison (it may be the node with the smallest d value)
	//Each while loop removes the node with the smallest d value, and then adds a new node that is not INF after the d value is changed
	//Because in the shortest path problem of positive weight graph, the loop must not be optimal, the traversed points can be eliminated directly 
	//This is very similar to the monotone queue mentioned in the previous chapters 
	void dijkstra(int s){priority_queue<HeapNode> Q;//Because it is a priority queue, the head of the queue is the element with the lowest d value 
		for (int i=0;i<n;i++) d[i]=INF; d[s]=0; memset(v,0,sizeof(v));
		Q.push((HeapNode){0,s});//Put the starting point in Q in advance 
		while (!Q.empty()){ HeapNode x=Q.top(); Q.pop();
			if (!v[x.u]) continue; v[x.u]=1;
			//Find the edge starting from node x.u through the edge list stored in vector array
			//Then update the d value and the path stored by p. since the d value is modified by comparison, it is no longer equal to INF
			//The modified node, whose d value is not INF, is put into the priority queue 
			//In fact, the marked node can be understood as "reachable node" 
			for (int i=0;i<G[x.u].size();i++) if (d[edges[G[x.u][i]].to]>d[x.u]+edges[G[x.u][i]].dist){
				d[edges[G[x.u][i].to]=d[x.u]+edges[G[x.u][i]].dist;//Modification of d value 
				p[edges[G[x.u][i].to]=G[x.u][i];//Modification of p value
				//In the current loop, the path from node u to the next node is G[x.u][i]
				//The structure composed of modified d value and node number is added to the monotone queue 
				Q.push((HeapNode){d[edges[G[x.u][i]].to],edges[G[x.u][i]].to});
			}
		}	
	}
}; 

The method of outputting the path in the book is very good, but if you think the space consumption is still too large, you can change the space with time and determine the precursor node of node i (dist[j]+w[j][i]=dist[i]) through the dist value until you trace back to the starting point.

In fact, the above method is generally not used.

Floyd algorithm

Also known as war shall algorithm, it is an algorithm for finding closure in binary relationship (see page p129 of discrete mathematics for details). The algorithm process is still relatively simple.

//Floyd algorithm, path[i][j] is the precursor node number of j in the shortest path from I to j 
void Floyd(MatGraph g){int A[MAXV][MAXV],path[MAXV][MAXV];
	for (int i=0;i<g.n;i++) for (int j=0;j<g.n;j++){	
		A[i][j]=g.edges[i][j];//path[i][j]=-1 indicates that there is no shortest path 
		if (i!=j&&g.edges[i][j]<INF) path[i][j]=i; else path[i][j]=-1; 
	}//k is equivalent to the division point added by the shortest path from i to j 
	for (int k=0;k<g.n;k++)	for (int i=0;i<g.n;i++) for (int j=0;j<g.n;j++) 
		if (A[i][j]>A[i][k]+A[k][j]){//The divided path is shorter, and the path from i to j is equal to the shortest path from i to k and k to J
		//The precursor node of the shortest path from i to j is changed to the precursor node of the shortest path from k to j, first from J to k, and then from k to J 
			A[i][j]=A[i][k]+A[k][j]; path[i][j]=path[k][j];		
	}Dispath(g,A,path);//Output shortest path
}

The method of output path is the same as that of Dijkstra algorithm.

There is also a bellman Ford algorithm to deal with the situation that negative edges will appear on the graph, which can exclude negative rings. See for interested information This article.