There are five commonly used shortest path algorithms in graph theory. They are coming. All the villains are coming 💣 The enemy has five seconds to reach the battlefield~ 
💓 On graph theory
Graph theory has a long history, but graph theory is an important concern in both company interview and programming competition. Now there may be many partners preparing for the Blue Bridge Cup. Here is the test point on graph theory pasted by the author from the official website of the Blue Bridge Cup. 
Graph theory is also a regular guest in the interview 
For this article, the author summarizes and shares the shortest path problem in the test site, and other graph theory problems continue to emerge in the followup~ 
🌟 Knowledge foreshadowing
🌻 Definition of graph
A graph is generally defined and described by a binary g = (V, e) or g = < V, E >. Where V is the set of vertices of graph G and E is the set of edges in graph G.

🌻 adjacency matrix
To put it more simply, it is to map the information given in the title to a twodimensional matrix. 
In combination with the above figure, point 0 can go to point 1. In the twodimensional matrix on the right, point 1 and point 0 on the position mark corresponding to (0,1) cannot go to point 2. Let (0,2) still be point 0, point 0 can go to point 3, let (0,3) mark 1, and so on 
🌻 Adjacency table
To be simple and rough is to string some connected points into a linked list according to the information given by the topic 
Still use the village example just now. Point 4 can go to points 2, 5 and 9, and then string them on a linked list. Write the whole 0 ~ 9 points side by side 
💓 General outline of shortest path algorithm
Friends, in this picture, you should keep in mind how to use the corresponding types of shortest path algorithms under different backgrounds and the time complexity of each shortest path algorithm 😉 
💓 dijkstra algorithm
🌟 Naive dijsktra algorithm (applicable to dense graphs)
🌻 Example description
It is stated in the title that there is no negative weight edge. According to the data range given in the title, there are few points and many edges. Therefore, it can be found that it is a dense graph, so it can be solved directly with the simple version of dijkstra. 
🌻 Reference code (C + + version)
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int N = 510; int n,m; //Points and edges in a graph int g[N][N]; //adjacency matrix int dist[N]; //Represents the distance from point 1 to each point in the figure bool st[N]; //Store the identified shortest point //Complete the function called void dijkstra() { memset(dist,0x3f,sizeof dist); //To process the distance array dist, first set all points to positive infinity dist[1] = 0; //Handle point 1, indicating that the distance from point 1 to point 1 is 0 //n1 cycles for(int i = 0; i < n1;i++) { int t = 1; //Process each point for(int j = 1; j <= n;j++) //If the current j is not in the st record status array //T = =  1  dist [t] > dist [j] means that this t was previously assigned by other j, and now a better one appears, or the value of this t has not been modified directly if(!st[j] && (t == 1  dist[t] > dist[j])) t = j; st[t] = true; //Put this point into the set //Use t to update the distance from other points to point 1 for(int j = 1; j <= n;j++) dist[j] = min(dist[j],dist[t]+g[t][j]); } } int main() { //Enter points and edges scanf("%d%d",&n,&m); //Initialize adjacency matrix memset(g,0x3f,sizeof g); //m times of inquiry and the process of drawing construction while(m) { int a,b,c; scanf("%d%d%d",&a,&b,&c); //Save to the drawing, just deal with the heavy edges g[a][b] = min(g[a][b],c); } //Call dijkstra dijkstra(); //Output results if(dist[n] == 0x3f3f3f3f) printf("%d",1); else printf("%d\n",dist[n]); return 0; }
🌻 Algorithm template
The specific operation flow of the simple dijkstra algorithm can be described in the following figure:
The specific code template of the simple dijkstra algorithm is as follows:
int g[N][N]; // Store each edge int dist[N]; // Store the shortest distance from point 1 to each point bool st[N]; // Store whether the shortest circuit of each point has been determined void dijkstra() { //Initialization link memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < n  1; i ++ ) { int t = 1; // Find the point with the smallest distance among the points where the shortest path has not been determined for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == 1  dist[t] > dist[j])) t = j; st[t] = true; // Update the distance of other points with the global minimum variable t for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], dist[t] + g[t][j]); } }
🌻 Detail implementation
1, Heavy edge
When building a graph, we need to focus on dealing with multiple edges, and finally only leave the shortest edge to build the graph 
while(m) { int a,b,c; scanf("%d%d%d",&a,&b,&c); /use min The function filters out the shortest edge to build the graph g[a][b] = min(g[a][b],c); }
2, The idea of initialization
Use the memset function to initialize the given address in bytes. Because it is to find the minimum path, initialize the distance from point 1 to each point as a large data, and finalize the distance from point 1 to point 1 as 0 
memset(dist,0x3f,sizeof dist); dist[1] = 0;
3, Find the point with the smallest distance among the points where the shortest path has not been determined
The core of the whole code is "! st[j]", and all operations are carried out at the point j currently ready to explore without being determined. 
For: int t = 1; It means that a variable t is declared to record the minimum value for the whole world. At the beginning, it is assigned a nonexistent  1. Using this minimum value to update all its outgoing edges is also carried out according to the idea of finding the global minimum value, so the shortest path can be obtained at last 
Finally, after all n points have been tried, put the global minimum variable t into the array st in which the shortest path state has been determined, "st[t] = true"
for (int i = 0; i < n  1; i ++ ) { int t = 1; for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == 1  dist[t] > dist[j])) t = j; st[t] = true;
😉 Happy Ac
🌟 Heap optimized dijkstra algorithm (applicable to sparse graph)
It can be seen from the above program code that its time complexity is O(n2). The main bottleneck affecting efficiency is to find the global minimum variable. Here, it enumerates next to next, and the efficiency will be relatively poor
Therefore, a heap can be used to maintain the dist array. The minimum value can be obtained in O(logn) time and deleted from the heap. Then an edge can be expanded and updated in O(logn) time. Finally, O(mlogn) can be used to realize the heap optimized version of dijkstra algorithm.
🌻 Example description
🌻 Reference implementation code (C + + version)
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; typedef pair<int,int> PII; //Use a pair number to maintain the distance and node number int n,m; const int N = 1e6+10; int h[N],e[N],ne[N],w[N],idx; //Sparse graph, saved with adjacency table int dist[N]; bool st[N]; void add(int a,int b ,int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; } void dijkstra() { //Initialization link memset(dist,0x3f,sizeof dist); dist[1] = 0; //Create a small root heap using the STL container priority_queue<PII,vector<PII>,greater<PII>> heap; heap.push({0,1}); //The first attribute of the number pair is the distance, and the second attribute is the node //Operate when the heap is not empty while(heap.size()) { //Take out the point with the smallest current distance each time. For the small root heap, that is, the top of the heap auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if(st[ver]) continue; //If this node is already in st, it means that redundant backup is being explored. Just skip it st[ver] =true; //Mark this node to determine the shortest path //Update other points with the current point for(int i = h[ver]; i != 1; i = ne[i]) { //Get the node stored in the adjacency table and store the node data in j int j = e[i]; //Start update if(dist[j] > distance + w[i]) { dist[j] = distance + w[i]; heap.push({dist[j],j}); //Insert the updated data into the heap } } } } int main() { //input scanf("%d%d",&n,&m); //Initialize adjacency table memset(h,1,sizeof h); //Construction drawing according to m edges while(m) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); } //Call dijkstra function dijkstra(); //output if(dist[n] == 0x3f3f3f3f) puts("1"); else printf("%d",dist[n]); return 0; }
🌻 Algorithm template
The operation flow of dijkstra algorithm of heap optimization version can be shown in the following figure:
The code of heap optimized dijkstra algorithm is described as follows:
typedef pair<int, int> PII; int n,m; // Number of points int h[N], w[N], e[N], ne[N], idx; // The adjacency table stores all edges int dist[N]; // Store the distance from all points to point 1 bool st[N]; // Is the shortest distance to store each point determined void dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1}); // first storage distance, second storage node number while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue; st[ver] = true; for (int i = h[ver]; i != 1; i = ne[i]) { int j = e[i]; if (dist[j] > distance + w[i]) { dist[j] = distance + w[i]; heap.push({dist[j], j}); } } } }
🌻 Detail implementation
1, Establishment of adjacency table
The idea is as like as two peas, but only one weight should be recorded. If you are not familiar with the static list, you can look at this buddy. 
Data structure  good helper for competition, static linked list
2, It is recommended to memorize the line of code for creating a small root heap
3, Data acquisition
After obtaining the heap top, continue to obtain the corresponding distance, node number and other data through the first and second attributes 
Chic Ac
💓 Bellman Ford algorithm
Look back at the algorithm outline 😉
Bellman Ford algorithm and SPFA algorithm are used in the context of single source and negative weight edge. On the whole, SPFA is better than Bellman Ford algorithm, but for the shortest path problem with limited number of edges, Bellman Ford algorithm can only be used 
🌻 Example description  shortest path with edge number limit
🌻 Reference code (C + + version)
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int N = 510 , M = 10010; int n,m,k; int dist[N]; int backup[N]; //Structure of storage point and weight struct Edge{ int a,b,w; }edges[M]; void bellman_ford() { //Initialization link memset(dist,0x3f,sizeof dist); dist[1] = 0; //Iterative kedges for(int i = 0 ; i < k ; i++) { //backups memcpy(backup,dist,sizeof dist); //Deal with the shortest circuit on each side for(int j = 0; j < m;j++) { //Get information for each point int a = edges[j].a,b = edges[j].b,w = edges[j].w; //Find shortest path dist[b] = min(dist[b],backup[a]+w); } } } int main() { //input scanf("%d%d%d",&n,&m,&k); //Mapping for(int i = 0; i < m ;i++) { int a,b,w; scanf("%d%d%d",&a,&b,&w); edges[i] = {a,b,w}; } //Call function bellman_ford(); //Output results if(dist[n] > 0x3f3f3f3f / 2) puts("impossible"); else printf("%d\n",dist[n]); return 0; }
🌻 Algorithm template
The flow chart of Bellman Ford algorithm implementation is as follows:
The bellman Ford algorithm code is described as follows:
int n, m; // n represents the number of points and m represents the number of sides int dist[N]; // dist[x] stores the shortest distance from 1 to X struct Edge // Edge, a represents the point, b represents the entry point, and w represents the weight of the edge { int a, b, w; }edges[M]; void bellman_ford() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; // If the nth iteration still relaxes the trigonometric inequality, it indicates that there is a shortest path with a length of n+1. According to the drawer principle, there are at least two identical points in the path, indicating that there is a negative weight loop in the graph. for (int i = 0; i < n; i ++ ) { for (int j = 0; j < m; j ++ ) { int a = edges[j].a, b = edges[j].b, w = edges[j].w; if (dist[b] > dist[a] + w) dist[b] = dist[a] + w; } } }
🌻 Detail implementation
1, Backup  in order to ensure that the condition of edge number limit can not be broken
memcpy(backup,dist,sizeof dist);
In order to avoid this, although the operation is indeed carried out under the number of sides k of the outer loop, a similar situation occurs when the inner loop goes to explore the point, so a backup operation is taken to curb this situation 
2, Happy Ac
💓 SPFA algorithm
spfa is usually called "Bellman Ford algorithm for queue optimization" internationally
🌻 Example description
🌻 Reference code (C + + version)
#include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int N = 100010; int n, m; int h[N], w[N], e[N], ne[N], idx; int dist[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } void spfa() { //Initialization link memset(dist, 0x3f, sizeof dist); dist[1] = 0; //Create a queue and queue point 1 that has confirmed the shortest path queue<int> q; q.push(1); //Mark points that have been queued st[1] = true; //Perform a series of operations when the queue is not empty while (q.size()) { //Get the team leader and get the team leader out of the team int t = q.front(); q.pop(); //Mark points that are not in the queue st[t] = false; //Use the team head to explore its exit for (int i = h[t]; i != 1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { //If the conditions are met, update the distance from point 1 to j dist[j] = dist[t] + w[i]; //If this point is not in the queue if (!st[j]) { //Join the team, mark q.push(j); st[j] = true; } } } } } int main() { //input scanf("%d%d", &n, &m); //Initialize adjacency table memset(h, 1, sizeof h); //Mapping while (m  ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } //Call function spfa(); //output if (dist[n] == 0x3f3f3f3f) puts("impossible"); else printf("%d\n", dist[n]); return 0; }
🌻 Algorithm template
The flow chart of SPFA algorithm implementation is as follows:
The code of SPFA algorithm is described as follows:
int n; // Total points int h[N], w[N], e[N], ne[N], idx; // The adjacency table stores all edges int dist[N]; // Store the shortest distance from each point to point 1 bool st[N]; // Stores whether each point is in the queue void spfa() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue<int> q; q.push(1); st[1] = true; while (q.size()) { auto t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != 1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) // If j already exists in the queue, there is no need to insert j repeatedly { q.push(j); st[j] = true; } } } } }
🌻 Detail implementation
1, Team entry and marking
After updating the new point j with t, remember to judge whether this point has been marked. If not, add it to the queue and put it into the st array for marking 
2, Associative memory
The essence of SPFA is to optimize the bellman Ford algorithm with queues, but the implementation is very similar to the heap optimized version of dijkstra algorithm, the queue for SPFA and the priority queue for dijkstra 
Happy Ac
💓 Floyd algorithm
In order to find the shortest path between any two points in the graph, that is Shortest path outline The shortest path problem of multiple sources and sinks in. For the shortest path problem between any two points, the graph is generally dense and the implementation is very simple.
The idea of Floyd algorithm:
Split the multisource shortest path into N times of single source shortest path.
In Dijkstra algorithm, the single source shortest path uses two cycles. The time complexity is O (N2). Floyd sets a layer of cycle n in the outermost layer, so the time complexity is O(n3)
🌻 Example description
🌻 Reference code (C + + version)
#include <cstring> #include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N = 210,INF = 1e9; int n,m, Q; int d[N][N]; void floyd() { for(int k = 1; k <= n;k++) for(int i = 1; i <= n;i++) for(int j = 1;j <= n;j++) d[i][j] = min(d[i][j],d[i][k]+d[k][j]); } int main() { scanf("%d%d%d",&n,&m,&Q); //Initialize adjacency matrix for(int i = 1;i <= n;i++) for(int j = 1; j <= n;j++) if(i == j) d[i][j] = 0; else d[i][j] = INF; //Create diagram while(m) { int a,b,c; scanf("%d%d%d",&a,&b,&c); d[a][b] = min(d[a][b],c); } //Call function floyd(); //Handle Q queries while(Q) { int a,b; scanf("%d%d",&a,&b); if(d[a][b] > INF / 2) puts("impossible"); else printf("%d\n",d[a][b]); } return 0; }
🌻 Algorithm template
Flow chart of Floyd algorithm implementation:
Floyd algorithm code Description:
initialization: for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF; // After the algorithm, d[a][b] represents the shortest distance from a to B void floyd() { for (int k = 1; k <= n; k ++ ) for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); }
🌻 Detail implementation
1, Initialization
if (i == j) d[i][j] = 0; else d[i][j] = INF;
d array represents the distance from i to j, so during initialization, i == j should be initialized to 0, and other positions should be initialized to an infinite number 
2, Output
Because the edge weight can be negative, d[a][b] is not necessarily INF, so the judgment condition is changed to d[a][b] is still a relatively large number 
if(d[a][b] > INF / 2) puts("impossible"); else printf("%d\n",d[a][b]);