The shortest path is divided into the single resource shortest path and the shortest path between two points, which are implemented by Dijkstra and Floyd algorithms respectively.

Dijkstra algorithm

That is, the shortest distance from one vertex to any other vertex

The following figure shows the path between A, B, C, D and E

If you want to find the shortest path between them using Dijkstra algorithm, you need to find the shortest distance between this vertex and other vertices, and then the “shortest vertex” (the shortest edge) keeps updating the shortest distance to other vertices, and then add new “shortest vertex”, after updating the shortest distance to other vertices, until finally, Find the shortest path from that point to the other vertices.

Note: Through the above steps, doesn’t it feel a bit like solving the prim algorithm for minimum spanning trees

Case process

Take node A as an example to find the shortest path to other nodes

1. First, assume that the straight-line distance from point A to other points is the shortest path, and A is added to set N (it will not be updated to be the shortest next time). The default is as follows

2. Compare the path between node A and other nodes, take the shortest path, here is a-b, add B to set N; In addition, starting from point B, the distance to other vertices outside the set N is compared. If the distance between (a-b edge) and (B to other vertices) is only smaller than the distance between A vertex and other vertices, the shortest distance to update is the sum of the distance from B to other vertices + (a-b), as shown below

3. In the last round, through the process of updating the distance between B and other vertices, we can find the shortest side between point B and other vertices, namely B-C, and add C to set N. At this time, as in Step 2, we can compare the distance between C and the vertex outside the set of N with the shortest distance updated previously. If it is shorter, the distance and the last node will be updated (only D and E are left outside the set at this time), otherwise the result will remain unchanged, as shown below

4. Through the previous round, through C process updates to other vertex distance, find the edge of the other vertices of the shortest C to C – E, will join the rest of the set N E, at this time as well as steps 2, 3, compared to N E the vertex distance outside collection, compared with the shortest distance update before, if the shorter the update on the distance and a node (set at this time only D), The results are shown below

5. The shortest paths to all nodes have been updated. The result is a single-resource shortest path

The result above stores the destination node and the previous node. In fact, if you want to find the full path, you only need to go through preNode until preNode is A, and then traverse backwards and forwards to obtain the full path

Code implementation

First, the code implementation is similar to the previous cases,

First declare the number of edge sets to save the result

typedef struct { int preNode; // Last node int node; // Destination node int weight; // Path length or weight} LSLineNode; // The basic structure of the edge array is preceded by the name, which is used more explicitly hereCopy the code

The steps for realizing the single-resource shortest path are as follows:

1. Declare that the shortest edge distance to other paths is min, the vertex index is M, and the resulting array is Nodes

2. Find the specified vertex V, go to the smallest edge of the other vertices, save the path to the set Nodes as the default result, and record the minimum value and its index

3. Mark vertex V and minimum vertex m as 1, indicating that they have joined set N

4. Start traversal

5. If flag is 1(in set N), continue skips to the next round; otherwise, proceed to the next step

6. Add the distance from the smallest vertex to the other vertices and check whether the sum is shorter than the shortest path previously calculated. If so, update the value and preNode; otherwise, do not update the preNode. And find the shortest edge of this process, find the smallest vertex, for subsequent use

7. Update the minimum vertex, the shortest edge is initially the maximum, so that the next round of updating the shortest path, the minimum vertex flag is marked as 1

8. Increment the variable and proceed to step 5 until the end of the loop, that is, all vertices are added to set N

// Dijkstra algorithm to solve, find the shortest edge, through the shortest edge to update the other shortest edge, recursion, the shortest path point from the default set N, to the shortest path set S, gradually update, Is very similar to prim algorithm void showSingleMinShortPathByDijkstra (int v) {v -; Int m = 0, min = MAXINT; int flag[N] = {0}; LSLineNode Nodes [N]; LSLineNode nodes[N]; For (int I = 0; for (int I = 0; i < N; i++) { nodes[i].weight = linesList[v][i]; nodes[i].node = i; nodes[i].preNode = v; if (nodes[i].weight < min) { m = i; min = nodes[i].weight; } } flag[v] = 1; // The default resource edge has been added to flag[m] = 1; Min = MAXINT; // Put the smallest edge in the set of S(flag). For (int I = 0; i < N; i++) { int temM = 0; For (int j = 0; for (int j = 0; j < N; J ++) {// If (flag[j]! = 0) continue; If (Nodes [m].weight + linesList[m][j] < nodes[j].weight) {nodes[j].weight = m; nodes[j].weight = nodes[m].weight + linesList[m][j]; } if (nodes[j].weight < min) { temM = j; min = nodes[j].weight; } } m = temM; flag[m] = 1; min = MAXINT; } // LSLineNode nodes is the shortest path printResult(Nodes, v); }Copy the code

If there is a preNode, you cannot directly obtain the completion path of the specified vertex to other vertices

Because there is a preNode, you can loop until preNode is the specified vertex, and then iterate until you reach the current vertex

Void printResult(LSLineNode *nodes, int v) {printf("\n dijkstra :\n"); void printResult(LSLineNode *nodes, int v) {"\n dijkstra :\n"); for (int i = 0; i < N; i++) { int result[N] = {nodes[i].node + 1, 0}; int j = i, k = 1; if (i ! = v) { while (nodes[j].preNode ! = v) { result[k++] = nodes[j].preNode + 1; j = nodes[j].preNode; } } result[k] = v + 1; for (; k >= 0; k--) { printf("%d%s", result[k], k == 0 ? "" :" - > "); } printf(": %d \n", nodes[i].weight); }}Copy the code

— Floyd

That is, the shortest distance between any two vertices, and the single-resource shortest path is the subset of its results

Therefore, the process of finding the shortest path between two points is similar to that of the single-resource shortest path. It only needs to continuously introduce one vertex after another as the intermediate node, which is similar to the single-resource shortest path and keeps updating all the other vertex distances. The updating process stores the shortest path between two points in the way of matrix. And store preNodes as matrices (or as a new edgeset infrastructure like single-resource shortest paths), as shown below

With A good understanding of single-resource shortest paths, this process should be very simple, as shown in the figure above, where indexes 0, 1, 2, 3, 4 are used instead of A, B, C, D, and E: The actual matrix graph is shown as below, and the preNode path graph, which points to itself or has no path, is marked -1, indicating that there is no shorter path, so the current index and can be directly taken

Referring to the index chart above, the implementation step logic is as follows:

1. Declare preNode 2d paths and shortest path weight matrix lines. The default adjacency matrix given by the system is linesList

2. Assign values to paths and lines at corresponding positions according to the adjacency matrix linesList given by the system, where preNode is the horizontal index. If the vertex is to itself or there is no path (the weight is 0 or ∞), then preNode is assigned -1

3. Introduce vertex M (default first vertex) and start the loop from the MTH vertex

4. Optimize the distance between vertex I and other vertices by taking the introduced vertex M as the intermediate point (minimum point)

5. Compare the sum of the distance from vertex I to point M and the distance from point M to other vertices with the distance directly from vertex to other vertices (same as single resource). If the distance is shorter, update the distance and preNode, otherwise not

6. Repeat step 5 to switch to the next vertex, namely i++, and adjust the other vertices through the introduced vertex m, i.e. return to step 5 and continue to perform backward

7. After updating the distances of other nodes through the introduced vertex M, introduce the next vertex (m+1) and continue to adjust the distances of other vertices, repeat Step 5

8. The introduction vertex M has reached the last vertex and ended directly, and the minimum path between two points has been generated

The code is as follows:

void showDoubleMinShortPathByFloyd(int start, int end) { int paths[N][N]; Int lines[N][N]; int lines[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { lines[i][j] = linesList[i][j]; if (i ! = j && lines[i][j] < MAXINT) { paths[i][j] = i; Else {paths[I][j] = 1; For (int k = 0; for (int k = 0; for (int k = 0; k < N; K ++) {//ik denotes the corresponding vertex coordinates, k denotes the newly added index for (int I = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (lines[i][k] + lines[k][j] < lines[i][j]) { lines[i][j] = lines[i][k] + lines[k][j]; paths[i][j] = k; // Record the optimized path (starting from 1, }}}}} void printPath(int lines[N][N], int paths[N][N], int start, Int end) {// Then the length of the shortest path is printf("\n Freud :\n"); printf("%d->", start + 1); int last = start; int next = paths[last][end]; while (next ! = -1 && next ! = last) { printf("%d-", next + 1); last = next; next = paths[next][end]; } printf("%d : %d\n", end + 1, lines[start][end]); Printf (" Generated path matrix :\n"); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { printf("%d ", paths[i][j] + 1); } printf("\n"); }}Copy the code