11.3 shortest circuit problem

In Chapter 9, we introduce the shortest path and longest path problem on weighted DAG and weighted DAG. Here we add rings to the graph.

11.3.1 Dijkstra algorithm

Dijkstra algorithm is applicable to the case where the edge weight is positive. It can be used to calculate the single source shortest path on the positive weight graph (that is, the shortest path from a single source point to all nodes). The algorithm is applicable to both directed and undirected graphs:

//Initialize all nodes as unmarked, set d[0]=0, and other d[i]=INF
//Cycle n times{
//	In all unlabeled nodes, select the node x with the smallest d value
//	Mark the node X and update d[y]=min{d[y],d[x]+w(x,y)} for the edge (x,y) divided from X 
//}
memset(v,0,sizeof(v));//Initialize the node, v[i]=1 indicates that the node is marked 
for (int i=0;i<n;i++) d[i]=(i==0?0:INF);
for (int i=0;i<n;i++){int x,mind=INF;//Min is the minimum d value 
	for (int y=0;y<n;y++) if (!v[y]&&d[y]<=mind) mind=d[x=y]; v[x]=1;
	//Here, for convenience, w[x][y]=INF is used to indicate that the edge (x,y) does not exist
	//Because d[y]=min{d[y],d[x]+w(x,y)} will not modify the value of d[y] 
	for (int y=0;y<n;y++) d[y]=min(d[y],d[x]+w[x][y]);
} 

In fact, it is the combination of dynamic programming and greedy method, but the complexity here is O(n2), which can be further optimized to O(mlogn)(m is the number of edges and n is the number of points). It is more suitable for sparse graphs (when m is large, we call it dense graphs).

In this representation, each node i has a linked list containing all edges starting from I: first number each edge, then save the number of the first edge of node u with first[u], and next[e] represents the number of the "next edge" of the edge numbered E (purple books generally do not like to use pointers, but use arrays to implement linked lists, trees and other data structures).

int n,m,first[maxn],u[maxm],v[maxm],w[maxm],next[maxm];
//first[i] represents the number of the first edge of node i, and next[e] represents the number of "next edge" of the edge numbered E 
//u[i] and v[i] represent the numbers of the left and right nodes of the edge numbered I
for (int i=0;i<n;i++) first[i]=-1;//Initialize header
for (int e=0;e<m;e++){cin>>u[e]>>v[e]>>w[e];
	next[e]=first[u[e]]; first[u[e]]=e;	//Insert linked list
} 

This insertion method is a little strange hhhh. Instead of determining the header once and inserting a new edge at the end of the table every time, insert the new edge to be inserted into the head of the table every time (take the original head of the table as the next edge of the new edge), and then modify the header number.

(it's actually head insertion hhhh)

It doesn't matter if you don't understand... In fact, the author of this book doesn't seem to like adjacency tables very much, so it's still written in vector and priority queue:

//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 value of d, 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 previous node of node i in the path 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 if the d value is not INF, it has 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 with a d value other than INF
	//It 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});
		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 in p. since the d value is modified by comparison, it must not be equal to INF
			//Put the modified node into the priority queue 
			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;
				p[edges[G[x.u][i].to]=G[x.u][i];
				Q.push((HeapNode){d[edges[G[x.u][i]].to],edges[G[x.u][i]].to});
			}
		}	
	}
};
 

Just have a look. I even doubt that I started to change the author here. I don't know why I suddenly started to package (I didn't understand what I wrote about modifying the path and nodes, because I didn't know what I pushed. If you really need to make further understanding, you'd better write it yourself).

Another point is that I don't use references to simplify the code, so it will look very complex.

11.3.2 Bellman Ford algorithm

Bellman Ford algorithm is to deal with the existence of negative weight (in fact, I really can't understand the concept of negative weight). Let's leave it here until there is an answer emmmm

11.3.3 Floyd algorithm

If you need the shortest path between every two points, you don't need to call Dijkstra algorithm or Bellman Ford algorithm n times. There is a simpler method - Floyd warhall algorithm (familiar? Familiar is right, there is this algorithm in the transfer closure of discrete mathematical relation matrix):

//Initialize d[i][i]=0, and other D values are INF
//The added if condition is used to avoid data overflow or the edge of INF really becomes the shortest part 
for (int k=0;k<n;k++) for (int i=0;i<n;i++) for (int j=0;j<n;j++) if (d[i][j]<INF&&d[k][j]<INF)
	d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

This proof is very simple (mathematical induction is not even needed, which feels intuitive). You can move your smart brain to know.

In fact, we used this algorithm as early as the self combination in Chapter 6 topo, but at that time we only considered whether there was a path between two points (i did similar problems one day and reversed the order of k, i and j HHH).

11.3.4 selected lectures on competition topics

11-4 telephone ring (UVA 247)

If two people call each other (directly or indirectly), they are in the same circle. Enter m calls of n people and find all circles.

Analysis: the data of n is small, and the maximum is only 25. After calculating the transitive closure with Floyd algorithm, output the owner of each connected component.

11-5 noise phobia (UVA 10048)

Enter an undirected weighted graph with C points and S edges. The edge weight represents the noise value of each path. When you go from one point to another, you always want the maximum noise value on the road to be the smallest. Enter some queries, ask two points each time, and output the path with the minimum maximum noise value between the two points.

Analysis: it is still Floyd algorithm, and the logical relationship is a little complex. d[i][j] is used to represent the minimum maximum noise value between I and j. then the state transition equation is as follows:

d[i][j]=min{max(d[i][k],d[k][j])}. It looks a little windy, but it's actually very simple.

Another question, wait until the bellman Ford algorithm is finished.