The data structure
Creates an adjacency matrix for the graph
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
Dijkstra algorithm for graph shortest path
Core idea of Dijkstra algorithm
-
Dijkstra algorithm is based on the idea of greedy algorithm. That is, the current iteration solution is always kept as the current optimal solution. It can also be regarded as a kind of dynamic programming idea, which always obtains the optimal solution under the current condition. When new conditions are added in the iteration to generate a new optimal solution, the optimal solution of the problem is updated. When we get to the last iteration, we get the global optimal solution. Because each iteration will refer to the previous optimal solution, repetitive work is reduced, data is effectively transferred, and the complexity of the overall work is reduced. In the shortest path problem, the local optimal solution is the current shortest path or the shortest distance from the starting point to other points under the current known conditions.
-
Dijkstra is mainly implemented by three one-dimensional arrays
- Final indicates whether V0 to a vertex Vm has found the mark of the shortest path. If so, final[m] = 1;
- Patharc P represents the subscript of the precursor of the current node. For example, if you go from V0 to V1, Patharc[1] = 0;
- ShortPathTable D stores the path from V0 to a vertex. The for loop prints the shortest path from V0 to Vm
/* Array used to store shortest path subscripts */ typedef int Patharc[MAXVEX]; / / typedef int ShortPathTable[MAXVEX]; / / typedef int ShortPathTable[MAXVEX]; Void ShortestPath_Dijkstra(MGraph G,int v0, Patharc *P,ShortPathTable *D){// Initialize int final[MAXVEX] = {0}; int i,w,k = 0,min; for ( i= 0; i<G.numVertexes; i++) { (*D)[i] = G.arc[v0][i]; (*P)[i] = 0; } // the current D is 0 1 5 # # # # # # // final, P is 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 // the path from V0 to V0 is V0 itself has no path (*D)[V0] = 0; //V0 to V0 has no path. Final [v0] = 1; (*P)[v0] = -1; For (I = 1; i<G.numVertexes ; I++){// min is initialized to INFINITYC min = INFINITYC; for(w=0; w<G.numVertexes; W++) {/ / to find the location of the minimum weight of the current D subscript k with him to record the if (final [w] = = 0 && (* D) [w] < min) {k = w; min = (*D)[w]; Final [k]=1; final[k]=1; // Based on the shortest path from v0 to v1, calculate the edge between v1 and other vertices, get the shortest distance between v0 and them for(w=0; w<G.numVertexes; W ++) {// If the path through v is shorter than the current path, update the current (*D)[w] the first time to 5 indicates that V0-> V2 directly to the weight of V1 ->V1 is 1, V1 ->V2 weight is 3 So the weight sum of V0->v1->v2 is 4, which is less than the previously stored 5 // At this time, the updated data of D[2] is 4, which means that the minimum path weight of V0->v2 is 4 // This loop means that it iterates through all the current vertices to find whether there is a path smaller than that of the directly connected vertices. If there is a path added to the array, the data is updated 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; }}}} int main(void) {printf("Dean shortest path -Dijkstra algorithm \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
Disadvantages of Dijkstra’s algorithm
Dijkstra algorithm can only get V0 to other vertices to the shortest path, while Floyd can get all to paths and the shortest path to the weight sum,Floyd therefore uses two-dimensional data storage
Floyd algorithm for graph shortest path
Core idea of Floyd algorithm
Floyd algorithm is a classical dynamic programming algorithm, also known as interpolation method. Is an algorithm that uses the idea of dynamic programming to find the shortest path between multiple source points in a given weighted graph. The algorithm aims to find the shortest path from point I to point J. Floyd algorithm mainly looks for whether there is an intermediate variable K that makes the current path have a smaller path
typedef int Patharc[MAXVEX][MAXVEX]; typedef int ShortPathTable[MAXVEX][MAXVEX]; void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D) { int v,w,k; /* initialize D and P matrices */ for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; + + w) {/ * D [v] [w] value is the weights between the corresponding points * / (* D) [v] [w] = G.a rc [v] [w]; /* P P[v][w] =w */ (*P)[v][w]=w */ (*P)[v][w]=w; }} //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 after the subscript k vertices path 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 one * / (*D)[v][w]=(*D)[v][k]+(*D)[k][w]; /* The path is set to pass through vertices with subscript k */ (*P)[v][w]=(*P)[v][k]; } } } } }Copy the code
Print the code in main
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\t",P[v][w]); } printf("\n"); } return 0; }Copy the code
Take V0 to V2 as an example
The sum of the shortest path weights is D[0][2], that is, 4 through the path is from V0, P[0][2] is 1, not 2
Therefore, 1 is the transit vertex, and the path becomes V0->V1. Then P[1][2] is 2 equal to 2
No transit vertices, exit search for transit vertices, the final path is V0->V1->V2