Topic overview and details
Single source shortest circuit, template, luoguP3371
Single source shortest circuit, template
dij algorithm
The core is to divide the nodes into two categories, one is to determine the shortest distance to the starting point, and the other is not determined
- Initially, none of them were determined
- Select a node with the shortest distance from the starting point from the nodes that are not determined
- Based on this point, determine the distance of other points that have not been updated
First, supplement the common values in the topic:
int -2^31=-21 4748 3648 to 2 ^ 31-1 = 21 4748 3647. There are 10 digits in total, and the maximum integer is expressed in hexadecimal 07fffff (32 bits in total, 4 bits in a group)
memset is to assign a value to a byte, for example:
int a[10]; memset(a,0x3f, sizeof(a));//In fact, each element in the a array is 0x3f3f3f3f. Sizeof returns the number of bytes occupied by a 40, that is, each byte is assigned 0x3f, and finally four bytes are combined into int
ps: the declared global variable is initialized to 0 by default, but not in the function
Since 0 is represented as 0x00 and - 1 is represented as 0xff by complement in the computer, the results obtained by the two memset operations are still the original, while 1 cannot.
The title states that the sum of all w is < 2 ^ 31, which means that the dis array can be an int array.
For this data 1 < = n < = 104, it needs about 100mb to store with adjacency matrix. It may be possible, but it has not been tried yet. (* * No, qwq * *, for most questions, if n > 104, you need to pay attention when applying for two-dimensional array) for another question 1 < = n < = 10 ^ 5, you can't use the adjacency matrix to store edges at all, so you use the chained forward star to simulate the adjacency table to store edges.
Whether using adjacency matrix or simulated adjacency table, the elements of single source shortest path are
- visit []: mark whether the optimal solution has been obtained
- dis []: stores the weight from the starting point to the point
Adjacency matrix method
Adjacency matrix dij
//Variable declaration
const int MaxN = 1002;//It depends on the subject
int dis[MaxN];
int visit[MaxN];
int e[MaxN][MaxN];//To store the relationship between edges, pay attention to the difference between directed graph and undirected graph when reading here, and initialize the corresponding value at the beginning
int n, m, s;//Number of points, number of sides, starting point
void dij(){
//Variable initialization
memset(dis, 0x3f, sizeof(dis));
memset(visit, 0, sizeof(visit));
dis[s] = 0;//Make the starting point be taken out first to update other edges
for(int k = 0; k < n;k++){//If one point is determined at a time, the result of n cycles must be determined
int u;//Record the current point closest to the starting point
int minNum = INT_MAX;//The header file < climits >, the maximum value of an integer, needs to be included
for(int i = 1; i <= n; i++){//Select the point closest to the starting point from the uncertain points
if(!visit[i] && minNum > dis[i]){
minNum = dis[i];
u = i;
}
visit[u] = 1;//The shortest distance of u from the starting point is determined
for(int i = 1; i <= n; i++){//Traverse all the adjacent points of u without determining the shortest distance. If the shortest distance through u is smaller than that without u, it will be updated
if(visit[i]){
continue;
}
if(dis[i] > dis[u] + e[u][i]){
dis[i] = dis[u] + e[u][i];
}
}
}
}
}
It can be seen that the adjacency matrix mainly uses it to traverse all the adjacency points of the selected u, as well as the weight of U - > I. Therefore, the data structure we choose only needs to be able to realize these two requirements to realize the algorithm.
- You can traverse all adjacent points of u
- You can know the weight of all edges
In the above algorithm, the process of selecting u can be optimized. You can use the priority queue in stl to select the point with the shortest distance from the starting point. We only need to queue the update node at each update (at this time, we need the shortest node and its distance to the starting point, so we need a node structure (including location and distance, that is, storage point) or the pair provided by stl as the element in the queue.
priority_queue
structural morphology
Heap optimized adjacency matrix dij
//structural morphology
struct node{
int pos;
int dis;
bool operator<(const node &x) const{//Overload < operator, custom priority, const must be added
return dis > x.dis;
}
}
priority_queue<int, int> pq;
void dij(){
memset(dis, 0x3f, sizeof(dis));
memset(visit, 0, sizeof(visit));
q.push_back(node{s, 0});
while(!q.empty()){//Here, you can also define a cnt variable to indicate that the cycle has been repeated several times, because each cycle determines the closest distance between a point and the starting point. Finally, if cnt < n, it indicates that the graph is not connected
node temp = q.top();//It's actually a heap, not a front
q.pop();
int u = temp.pos;
int d = temp.dis;//At this time, it is equivalent to the result of minimizing the loop above. Because there is another limitation above, that is, select the point with the shortest distance from the starting point among the nodes that have not been visited. Therefore, it is necessary to judge that if u has been determined, continue the next loop
if(visit[u]){
continue;
}
visit[u] = 1;
for(int i = 1; i <= n; i++){
if(visit[i]){
continue;
}
if(dis[i] > dis[u] + e[u][i]){
dis[i] = dis[u] + e[u][i];
pq.push(i, dis[i]);
}
}
}
}
Output the shortest path from the starting point to a node
It is necessary to record an array pre that records node precursors. The precursors of each node are initialized by themselves (this is also the condition for stopping at the last backtracking)
When updating pre, it is obvious that after determining the shortest node and updating the distance from other points to the starting point, pre[i] = u
//Output path, using vector to record the path
vector<int> res;
void getPath(int d){
if(pre[d] == d){
return;
}
getPath(pre[d]);
res.push_back(pre[d]);//Finally, you need to put the end point into res
}
Multi priority solution
In a slightly more complex topic, except that the topic requires the shortest distance from the starting point, if it is the same, choose a larger path * * (price, passing through more nodes), which only needs to add an else if branch when judging whether the node can be updated, judge the size of other conditions from the starting point when the distance is the same, and then judge whether to update.
Chain forward star method
Chained forward star map
A graph consists of points and edges, most of which have weights. Therefore, by storing these three parts, we can master a graph and have the function of traversing its adjacent vertices from a known vertex. For the ordinary adjacency matrix, the process of traversing one row is the process of traversing the adjacent vertices. The element value is the weight. It is obviously too wasteful in sparse graphs.
For the chain forward star, we use the structure egde to represent the edge, the auxiliary array head to represent the storage subscript of the last edge starting from i, and some global cnt subscripts to add the edge
const int MAXN=1002;
int head[i], int cnt = 1;//Initialize to - 1
struct edge{
int next;//Subscript of the previous edge with the same starting point as u
int to;//The end of the i-th side
int w;
}e[MAXN];
void addEdge(int u, int v, int w){
e[cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt++;
}
Ordinary dij
void dij(){
memset(dis, 0x3f, sizeof(dis));
memset(visit, 0, sizeof(visit));
dis[s] = 0;
for(int k = 0; k < n; k++){
int u, minNum = INT_MAX;
for(int i = 1; i < n; i++){
if(!visit[i] && minNum > dis[i]){
u = i;
minNum = dis[i];
}
}
visit[u] = 1;
For (int i = head [u]; I! = - 1; I = E [i]. Next) {/ / traverse each edge connected to u
int y = e[i].to;
if(visit[y]){
continue;
}
if(dis[y] > dis[u] + e[i].w){
dis[y] = dis[u] + e[i].w;
}
}
}
}
dij for heap optimization
//node and priority_ The queue is consistent with the above
void dij(){
memset(dis, 0x3f, sizeof(dis));
memset(visit, 0, sizeof(visit));
dis[s] = 0;
pq.push(node{s, 0});
while(!pq.empty()){
node temp = pq.top();
pq.pop();
int u = temp.pos;
//int d = temp.dis;
if(visit[u]){
continue;
}
visit[u] = 1;
for(int i = head[u]; i != -1; i = e[i].next()){
int y = e[i].to;
if(dis[y] > dis[u] + e[i].w){
dis[y] = dis[u] + e[i].w;
pq.push(node{y,dis[u]});
}
}
}
}
Solution of vector simulated adjacency table
The vector array is mainly used to store the nodes connected by each edge and the weight of this edge. Therefore, it is necessary to customize a node2 structure to represent the end point and weight, so as to facilitate the subsequent query.
struct node2{
int to;
int w;
};
vector<node> v[MAXN];
void dij(){
memset(dis, 0x3f, sizeof(dis));
pq.push(node2{s, 0});
dis[s] = 0;
while(!pq.empty()){
node2 temp = pq.top();
pq.pop();
int u = temp.pos;
if(visit[u]){
continue;
}
visit[u] = 1;
for(int i = 0;i < v[u].size();i++){
int y = v[u][i].to;
if(visit[y]){
continue;
}
if(dis[y] > dis[u] + v[u][i].w){
dis[y] = dis[u] + v[u][i].w;
pq.push(node2{y, dis[y]});
}
}
}
}
Daily small code review and sorting
Fast power mod
luogup1226
Observation topic only a may explode in the calculation process
typedef long long ll;
int fp(ll a, int p, int m){//Some topics have to be long long,
int res = 1;
while(p){
if(p & 1){
res = res * a % m;
}
a = a * a % m;
p /= 2;
}
return res;
}
Solving Fibonacci sequence
Rolling Division
int gcd(int a, int b){
return b == 0 : a ? gcd(b, a % b);
}
Reference blog
Chain forward star understanding
priority_queue usage
Fast power understanding
Little sentiment
Since learning the algorithm, I have encountered a lot of setbacks. I basically become the denominator every time. But slowly I understand that everyone's starting point is fast and full. Before college, I didn't even know what C language is, and there were more than 70 freshmen in C language. Later, I learned about the algorithm competition, even the trials in the school. In this way, the fear of algorithm learning planted the seeds. As a sophomore, I still want to improve my programming ability, but my progress is slow. Until now, I slowly feel that learning algorithms, on the one hand, is for future employment, on the other hand, I will really enjoy the fun of debugging code and exercising my thinking. I don't pay attention to how strong others are. Now I just want to learn the real knowledge and the subtlety of the algorithm. I was really impressed when I found that I filled in a line of code to record the nodes returned in the original way, so as to solve my own problem. I'm really happy to see some ideas on the topic slowly. After that, I will continue to move forward and enrich my knowledge.
In addition, I also slowly learned that compared with my future life and work, the failure and unhappiness at this stage are not worth being sad. They just point out the direction for my progress. In the face of life, it is very important to have your own goals, interests, things you like to do, and independent thinking.
The world is so big that those who are stronger than themselves can be found everywhere. But I will still face learning and life with confidence, because I need to make myself the image of my heart. (do what you like, love life, study healthily and make your family happy)