Contents
前言
At first glance, the search can find the shortest distance from one point to another like this one, but some problems can be solved by both, while other searches cannot. The search has a definite direction, step by step, and the shortest A road tells you that you can walk directly from two points, without a definite direction. The shortest path problem, in layman's terms, is to give you n points and m edges, and then find the shortest distance between two points. There are three algorithms commonly used to solve the shortest path: Floyd, Dijkstra, and SPFA. Each of the three methods has its own advantages and disadvantages
- Floyd's algorithm is a multi-source shortest path algorithm with the highest complexity (n^3). It is usually used in problems with relatively few points and unfixed starting points. It can solve negative edges (negative weights) but cannot solve negative loops.
- Dijkstra's algorithm is a single-source shortest path algorithm. The most commonly used time complexity (n^2) can reach (nlogn) after optimization. It cannot solve the negative edge problem. Sparse graphs (the range of points is large but there are not many edges). |E| is much smaller than |V|²) and requires more space.
- The SPFA algorithm is suitable for sparse graphs and can solve problems with negative weighted edges and negative rings, but it is less efficient than Dijkstra in dense graphs.
Floyd algorithm
Floyd's algorithm is relatively simple. It violently enumerates all possibilities. After searching all possibilities, you can find the shortest path between two points.
Parameter explanation
- Chara array: stores the distance between two points. The value of Chara[i][j] is the distance from point i to point j.
- n: There are n points in total.
- p[i][j]: Precursor matrix representing the minimum path corresponding to the vertex
- MAX: Define the maximum value. If the road is blocked, the distance is MAX.
Algorithmic thinking
It is easy to understand that there are only two ways for us to go from one point i to another point j.
- directly from i to j
- Transfer through intermediate point k, i->k->j
So we iterate through all situations, and if the distance through a certain transfer point is less than the distance directly reached, update the distance between the two points.
if(Chara[i][j] > Chara[i][k] + Chara[k][j])
Chara[i][j] = Chara[i][k] + Chara[k][j];代码
#define MAX 65535
int Chara[N][N], p[N][N];
int n, m;
void Floyd() {
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
p[i][j]=j;//初始化
for(int k = 0; k < n; k++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(Chara[i][k] == MAX || Chara[k][j] == MAX)
continue;
if(Chara[i][j] > Chara[i][k] + Chara[k][j]) {
//如果经过下标k顶点路径比原两点间路径更短
//将当前两点权值设为更小的那一个
Chara[i][j] = Chara[i][k] + Chara[k][j];
p[i][j] = p[i][k];//路径设置经过下标k的顶点
}
}
}
}
}
Dijkstra's algorithm
Dijkstra's algorithm is implemented by greedy thinking. First, save the distance from the starting point to all points to find the shortest one, and then relax it once to find the shortest one. The so-called relaxation operation is to traverse it once and look at the point with the shortest distance just found as Will the transfer station be closer? If it is closer, update the distance. In this way, after searching all the points, the shortest distance from the starting point to all other points will be saved.
Parameter explanation
- Chara array: stores the distance between two points. The value of Chara[i][j] is the distance from point i to point j.
- dis array: stores the distance from the starting point to each point, dis[i] is the distance from the starting point to point i.
- vis array: whether the marker point has been visited
- INF: The maximum value defined by the macro is blocked.
Algorithmic thinking
There are two arrays. For the meaning of dis and vis, see above. Initially, there is only the starting point in vis. Update the distance from the starting point in dis to all points.
Traverse all nodes, find the point K closest to the starting point, and add this point to the vis mark
Perform a relaxation operation, traverse all other points that are not in the vis array, and compare the distance between the starting point -> this point and the starting point -> K point -> this point.
Repeat operations 2-3 until all points have been traversed
代码
#define INF 65535
int n, m, s, t;
int Chara[N][N], dis[N], vis[N], p[i];
void Dijkstra(int src) { //src传入的起点
for(int i = 0; i < m; i++) { //初始化起点到所有点的距离
dis[i] = Chara[src][i];
vis[i] = 0;
p[i]=0;
}
dis[src] = 0; //到自身距离为0
vis[src] = 1; //标记 注src=0
for(int i = 0; i < m; i++) {
int ans = INF, k;
for(int j = 0; j < m; j++) { // 寻找未被访问过距离起点v0最近的
if(!vis[j] && dis[j] < ans) {
k = j;
ans = dis[j];
}
}
vis[k] = 1; //标记已访问
if(ans == INF) break; //表示剩下所有点都不通
for(int j = 0; j < m; j++) {
//松弛操作，更新起点到所有未访问点的距离
if(!vis[j] && dis[k] + Chara[k][j] < dis[j] ) {
dis[j] = dis[k] + Chara[k][j];
p[j]=k;//存放前驱节点
}
}
}
}forward star version
int dij(int u) {
dis[u] = 0;
while(true) {
int k = -1;
int min = INF;
for(int i = 0; i < n; i++) {
if(!vis[i] && dis[i] < min) {
min = dis[i];
k = i;
}
}
if(k == -1) break;
vis[k] = true;
for(int i = head[k]; ~i; i = edge[i].nxt) {
if(!vis[edge[i].v] && dis[k] + edge[i].w < dis[edge[i].v]) {
dis[edge[i].v] = dis[k] + edge[i].w;
}
}
}
}SPFA algorithm
SPFA is a BF algorithm that uses queue optimization. It looks very similar to BFS. BF is less efficient and I will not introduce it. There is also an SPFA that uses DFS to optimize BF. However, this method is often more degraded than usual and is not as good as queue optimization. Yes, SPFA is enough for normal use. It can solve the negative edge problem and determine whether a negative loop exists. In sparse graphs, storage similar to adjacency linked lists saves space.
Parameter explanation
- Node structure: used to store edges. The array subscript represents the starting point of the edge. The v in the structure represents the end point of the edge. Weight/w represents the weight.
- dis array: stores the distance from the starting point to each point, dis[i] is the distance from the starting point to point i.
- vis array: whether the marker point has been visited
- INF: The maximum value defined by the macro is blocked.
Algorithmic thinking
- Initially, only the starting point is put into the queue.
- Traverse the edges connected to the starting point, update the distance dis[] if it can be relaxed, and then judge if the point is not in the queue and mark it in the queue.
- Leave the head of the team, cancel the mark, and loop through 2-3 steps until the team is empty.
- All updateable points have been updated, and the distance in the dis[] array is the shortest distance from the starting point to other points.
Why SPFA can handle negative edges: Because in SPFA, after each point is relaxed, it means that the point is closer, so it is possible that other points will be optimized again through this point, so this point is added to the queue and judged again, while in Dijkstra it is The greedy strategy will not update after each point is selected. If a negative edge is encountered, this greedy strategy will be destroyed and cannot be processed. How to judge a loop: When storing edges, record the in-degree of each point. Record each point once when it joins the queue. If the number of times it joins is greater than the in-degree of this point, it means it entered twice from a certain road. , that is, a loop is formed at this point.
代码
const int INF = 0x3f3f3f3f;
const int N = 210;
int n, m, s, t;
int dis[N], vis[N], sum[N];
struct node {
int v; //点
int weight; //权值
};
vector<node> mp[N]; //储存边;
//SPFA写法
void SPFA(int src) {
int q;
queue<int> Q;
vis[src] = 1;
dis[src] = 0;
Q.push(src);
while(!Q.empty()) {
q = Q.front();
Q.pop();
vis[q] = 0;
for(int i = 0; i < mp[q].size(); i++) {
if(dis[q] + mp[q][i].weight < dis[mp[q][i].v]) {
dis[mp[q][i].v] = dis[q] + mp[q][i].weight;
if(!vis[mp[q][i].v]) {
Q.push(mp[q][i].v);
vis[mp[q][i].v] = 1;
}
}
}
}
return;
}