For the basic knowledge of graphs and their storage-related implementation, as well as other related knowledge of data structures and algorithms, please see the article “Summary of Basic Knowledge of Data Structures and Algorithms”.

Graph shortest path

The shortest path of a graph refers to the shortest path and the weight of the edge through which the connection passes between any two vertices in a connected graph.

This article explains two ways to find the shortest path of graph: Dijkstra algorithm and Floyd algorithm.

Dijkstra algorithm

1. Algorithm idea

Step 1: Starting from V0, V1 and V2 are connected to V0, and the weights of edges are 1 and 5 respectively. Since 1 is smaller than 5, V1 is selected, and the sum of the weights of the edges passed by at this time is recorded as sum = 1. V0 and V1 are marked as having added the shortest path

Step 2: The vertices connected with V1 are V2, V3, V4, and the weights of edges are 3, 5, 7, and the minimum is 3. Therefore, select vertex V2, sum + 3 = 4, and record that V2 has been added to the shortest path

Step 3: The vertices connected to V2 are V4 and V5, the weights of edges are 1 and 7, and the minimum is 1. Therefore, select vertex V4, sum+1 = 5, and record that V4 has added the shortest path

Step 4: the vertices V3, V5, V6, V7 connected to V4 and not added to the shortest path have weights of 2, 3, 6, 9, and the minimum is 2. Therefore, choose V3, sum + 2 = 7, and record that V3 has added to the shortest path

Step 5: the vertex that is connected to V3 and does not add the shortest path is V6, and the weight of the edge is 3, so V6 can only be selected, sum + 3 = 10, and record that V6 has added the shortest path

Step 6: The vertices connected to V6 that are not added to the shortest path are V7 and V8, and the weights of edges are 4 and 7, and the minimum is 4, so select V7, sum + 2 = 12, and record that V7 has added to the shortest path

Step 7: AndV7The connected vertices that are not added to the shortest path areV5, V8And the weight of the edge is5, 4,.The minimumIs 4, so chooseV4, sum + 4 = 16, records that V8 has added the shortest path.

After the above steps, we finally get fromWhere V0 to V8theThe shortest pathandWeights andTo:

• The shortest path: where V0 – > V1 – > V2 – > – > V3 – > V4 V6 – > V7 – > V8.
• The sum of weights: 1 + 3 + 1 + 2 + 3 + 2 + 4 = 16.

Although we finally got the correct result, there are still some loopholes in the above analysis process, such as:

• 1. What if the weights of V7 and V5 are less than those of V7 and V8?
• 2. What if the weights of V6 and V8 are less than those of V6 and V7 +V7 and V8?
• 3. What do you think?

As a matter of fact, the previous analysis only roughly describes the idea of Dijkstra’s algorithm, not the real process. The reason for this idea is to give readers a preliminary understanding of Dijkstra’s algorithm idea. Next, we will further explain the implementation logic of Dijkstra’s algorithm.

2. Code logic

1. First use the sequential storage of adjacency matrix to store the graph in memory

2. Design three arrays to realize the solution steps in the algorithm idea, and update these three arrays during the solution process

• 1.Final array: indicates whether V0 to the vertex VwalreadyobtainedThe flag of the shortest path, if the result has been obtained, then markfinal[w] = 1; Final arrays are initialized with all elements equal to 0.
• 2.D array: of all edges passing through V0 to the vertex VwWeights andtheThe minimum valueAs we solve, this minimum will keep going upupdateUpdate when a value smaller than the one currently stored is encountered. The initial value of the D array is the array of edge tables that V0 corresponds to in the adjacency matrix, because initially the weights of the vertices connected to V0 can only be determined by the array of edge tables.

• 3.P arrayThe index value of the: P array represents all the values in the graphThe subscript value of the vertex, the value in P array represents the subscript of the precursors of the vertices corresponding to the index. The initial values of P array are all 0, indicating that the precursors of all vertices are 0.

As shown in the figure above, V0 has no precursor, so P[0] = -1, V1’s precursor is V0, so P[1] = 0,V2, V3, V4’s precursor is V1, so P[2], P[3], P[3] = 1, although the precursor of the three vertices are all 1, However, in the shortest path, one vertex can only be the precursor of another unique vertex, so the P array will be updated during the algorithm solving process, please look for the final result.

3. Code implementation

Define some state values and data types

#define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXEDGE 20 #define MAXVEX 20 #define INFINITYC 65535  typedef int Status; // Typedef int Patharc[MAXVEX]; // Typedefs int ShortPathTable[MAXVEX]; // Typedefs int ShortPathTable[MAXVEX];Copy the code

2. Data structure design for sequential storage of adjacency matrix

typedef struct { int vexs[MAXVEX]; Int arc[MAXVEX][MAXVEX]; Int numVertexes, numEdges; }MGraph;Copy the code

3. Realization of sequential storage of adjacency matrix

void CreateMGraph(MGraph *G) { int i, j; G->numEdges=16; G->numVertexes=9; for(i = 0; i < G->numVertexes; i++) { G->vexs[i]=i; } for(i = 0; i < G->numVertexes; i++) { for( j = 0; j < G->numVertexes; j++) { if(i==j) G->arc[i][j]=0; else G->arc[i][j] = G->arc[j][i] = INFINITYC; } } G->arc[0][1]=1; G->arc[0][2]=5; G->arc[1][2]=3; G->arc[1][3]=7; G->arc[1][4]=5; G->arc[2][4]=1; G->arc[2][5]=7; G->arc[3][4]=2; G->arc[3][6]=3; G->arc[4][5]=3; G->arc[4][6]=6; G->arc[4][7]=9; G->arc[5][7]=5; G->arc[6][7]=2; G->arc[6][8]=7; G->arc[7][8]=4; for(i = 0; i < G->numVertexes; i++) { for(j = i; j < G->numVertexes; j++) { G->arc[j][i] =G->arc[i][j]; }}}Copy the code

4.Dijkstra algorithm code implementation

/* get the shortest path between 2 points in the network graph Dijkstra algorithm G: network graph; V0: the vertex starting from v0; P [v]: precursor vertex subindex; D[v]: represents the sum of the shortest path length from V0 to v; */ void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D) { int v,w,k,min; k = 0; //final[w] = 1 int final[MAXVEX]; //1. Initialize data for(v=0; v<G.numVertexes; V ++) {// All vertices initialized to unknown shortest path state 0 final[v] = 0; (*D)[v] = g.arc [v] [v]; (*D)[v] = g.arc [v] [v]; // initialize path array p = 0 (* p)[v] = 0; } // the path from V0 to V0 is 0 (*D)[V0] = 0; Final [V0] = 1; final[V0] = 1; //v0 has no precursor vertex, record -1 (*P)[v0] = -1; NumVertexes -1 for(v = 1; v < G.numVertexes; V++) {// min=INFINITYC; For (w=0; for(w=0; w<G.numVertexes; w++) { if(! final[w] && (*D)[w]< min) { k=w; // min = (*D)[w]; }} // Mark the nearest vertex found so far as 1; final[k] = 1; K for(w=0; k for(w=0; w=0; w<G.numVertexes; W++) {// if the path through v is shorter than the current path, update if(! Final [w] && (min + G.a rc [k] [w] < (* D) [w]) {/ / find a shorter path, then modify the D [w], [w] / P/modify the current path length (* D) [w] = min + G.a rc [k] [w]; (*P)[w] = k; //w is preceded by k}}}}Copy the code

5. Debug code

Int main(void) {printf(" shortest path-dijkstra \n"); int i,j,v0; MGraph G; Patharc P; ShortPathTable D; v0 = 0; CreateMGraph(&G); ShortestPath_Dijkstra(G, v0, &P, &D); Printf (" Shortest path path :\n"); for(i=1; i<G.numVertexes; ++i) { printf("v%d -> v%d : ",v0,i); j = i; while(P[j] ! = -1) { printf("%d ",P[j]); j = P[j]; } printf("\n"); } printf("\n shortest path weights and \n"); for(i=1; i<G.numVertexes; ++i) printf("v%d -> v%d : %d \n",G.vexs[0],G.vexs[i],D[i]); printf("\n"); return 0; }Copy the code

Execution Result:

Through Dijkstra algorithm, the shortest path between V0 and any vertex is finally obtained. The limitation of this algorithm is that you need to store data in the adjacency matrix with a specified vertex as the 0th memory, and can only find the shortest path between the specified vertex and any vertex. The Floyd algorithm introduced later can solve the shortest path between any two vertices.

4. Execution process

First execution

Changes in data during code executionThe shortest path changes in the graph

Second execution

Changes in data during code execution

The shortest path changes in the graph

Third execution

Changes in data during code execution

Graph shortest path changes

Fourth execution

Changes in data during code execution

Graph shortest path changes

Fifth execution

Changes in data during code execution

Graph shortest path changes

Sixth Execution

Changes in data during code execution

Graph shortest path changes

Seventh Execution

Changes in data during code execution

Graph shortest path changes

Eighth Execution

Changes in data during code executionGraph shortest path changes

Finally, the data of D array and P array are:

5. Summary

• 1.Dijkstra algorithmOnly to solveSpecified vertexTo the otherAny vertexIs the shortest path and the corresponding weight;
• 2.Dijkstra algorithmThe desires ofSpecified vertexThe data must be stored in the adjacency matrixThe zerothLocation of memory.

Third, Floyd algorithm

1. Algorithm idea

This same graph is now stored in memory by the order of the adjacency matrix

• 1. First of all, we know thatConnected graphIn theAny vertexCan go through a finite number of edges and any other vertex in the graphConnected to a;
• 2. Adjacency matrix description is arbitraryTwo verticesA direct connection between verticesSelf and selfThe weight of the edge when it’s joined0;Vertices and verticesWhen you have a connection, the weight of an edge is oneNon-infinity greater than 0Numerical value; Between vertices and verticesThere is noWhen directly connected, the weight of the edge isinfinity;
• (3)1 and 2Two conditions, so for the diagramAny twoVertices can pass through other verticesAny oneVertex orMultiple connectedVertex connection of; When two vertices are directly connected, theirEdge weightsThere may beIs greater thanthroughAnother vertexorConnected verticesOf the connected sidesWeights and. If we couldthroughThe otherOne or moreVertex toThe targetVertex, and the experienced edgeWeights andOver the weight of the edge that goes directly to the corresponding vertexsmaller“Then we have a choiceBetter pathExamples are as follows:

Suppose there are only three vertices V0, V1 and V2 in the figure above, and their storage in the adjacency matrix is as shown in the figure above. According to the figure, the weight of the edge directly from V1 to V2 is 5, which is reflected in the adjacency matrix as D[1][2] = 5. The sum of weights from V1 to V0 to V2 is 2+1 = 3, and 3 is less than 5, so when we need to find the shortest path from V1 to V2, we can choose V1->V0->V2.

• 4. On the basis of three ideas for the complete graph is presented to solve the shortest path, we can through the figure of a vertex as intermediate vertex, respectively to solve the boundary between any two vertices in the graph of the weights and, if the weight and smaller than previously plan, you can update the edge between two vertices of a weight;
• 5. When we encounter infinity, it means that two vertices do not need to be connected by another vertex, so we do not need to update the weight of the edge of the two vertices.

Through the above analysis, we need to determine whether the sum of weights between two vertices is less than the sum of weights connected by one or more other vertices. The following formula is provided:

The sum of the weights between vertices V and W, take the weights of v and W, and the weights of v and O plus the smaller weights of O and W.

2. Code implementation ideas

• 1. The design2 d arrayD, for recording between verticesA weight, its initial value is set to the data of the graph’s adjacency matrix; In the implementation of the algorithm, yesConstant updating, the final result is the weight and of the shortest path between any two vertices;
• 2. Design one2 d arrayP, which is used torecordBetween any two verticesThe shortest pathThe peak of theThe subscript; Its initial value is the corresponding column value for each column, indicating that the corresponding vertices of the column are connected to other vertices by the corresponding vertices of the column, that is, there is no connection.

3. Code implementation

1. Diagram storage

The sequential storage of adjacency matrix has been introduced in Dijkstra algorithm

2. Definition of D and P arrays

typedef int Patharc[MAXVEX][MAXVEX];

typedef int ShortPathTable[MAXVEX][MAXVEX];
Copy the code

3. Implementation of Floyd algorithm

void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D) { int v,w,k; //1. Initialize D and P matrices for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; + + w) {/ / D [v] [w] to the edge of adjacency matrix table array values (* D) [v] [w] = G.a rc [v] [w]; P P[v][w] =w (*P)[v][w]=w; }} //2. K represents the transit vertex for(k=0; k<G.numVertexes; ++k) { for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; + + w) {/ / if the subscript k vertices route shorter than the original path between two points if (D) (* [v] [w] > (* D) [v] [k] + (* D) [k] [w]) {/ / the current weights between two points is set to a smaller (* D) [v] [w] = (* D) [v] + [k] (*D)[k][w]; // The path is set to pass through the vertex with index k (*P)[v][w] = (*P)[v][k]; } } } } }Copy the code

4. Mode code

Int main(void) {printf("Hello, shortest path Floyd algorithm "); int v,w,k; MGraph G; Patharc P; ShortPathTable D; // CreateMGraph(&g); ShortestPath_Floyd(G,&P,&D); // Prints all possible shortest paths between vertices and the path values printf(" Shortest paths between vertices are as follows :\n"); for(v=0; v<G.numVertexes; ++v) { for(w=v+1; w<G.numVertexes; w++) { printf("v%d-v%d weight: %d ",v,w,D[v][w]); // obtain the first path vertex subscript k=P[v][w]; // Print the source point printf(" path: %d",v); // If path vertex subscript is not terminal while(k! Printf (" -> %d",k); // Get the next path vertex subscript k=P[k][w]; } // printf(" -> %d\n",w); } printf("\n"); Printf (" shortest path D array \n"); for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { printf("%d\t",D[v][w]); } printf("\n"); Printf (" shortest path P array \n"); for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { printf("%d ",P[v][w]); } printf("\n"); } return 0; }Copy the code

5. Execution result

Through the above algorithm, the values of D array and P array are finally obtained:

4. Summary

Floyd algorithm solves the shortest path of any two vertices.

Four,

The shortest path of the graph is calculated by Dijkstra algorithm and Floyd algorithm. Both algorithms are very difficult to understand, so readers can experience more.