Article directory
- What is Dijkstra’s algorithm
-
- Origin of algorithm
- The purpose of the algorithm
- The theory of Dijkstra’s algorithm
- Implementation of Dijkstra’s algorithm
-
- Macro definition
- Prerequisite function implementation
- Dijkstra’s algorithm
- Main function implementation
- Debugging results
- Code analysis
Life has blocked us. As long as our hearts are not dead, life will never be a pool of stagnant water, and we will still bloom in our most beautiful posture.
What is Dijkstra’s algorithm
Origin of algorithm
Dijkstra’s algorithm (English: Dijkstra’s algorithm), also known as Dijkstra’s algorithm and Dijkstra’s algorithm, is an algorithm discovered by Dutch computer scientist Edsgel Dijkstra in 1956. And it was published in a journal 3 years later. Dijkstra’s algorithm uses a method similar to breadth-first search to solve the single-source shortest path problem in weighted graphs.
There are many variations of this algorithm: Dijkstra’s original version only worked to find the shortest path between two vertices, later, more common variations fixed one vertex as the source node and then found that vertex to all nodes in the graph. The shortest paths to other nodes generate a shortest path tree.
Use of algorithm
This algorithm solves the weighted single-source shortest path problem on the graph. Specifically, Dijkstra’s algorithm sets a vertex set S, and the final shortest path weights between all vertices in the set S and the source point s have been determined. This algorithm is often used in routing algorithms or as a submodule of other graph algorithms. For example, if the vertices in the graph represent cities and the weights on the edges represent the driving distance between the cities, this algorithm can be used to find the shortest path between the two cities.
The theory of Dijkstra’s algorithm
First, take the example 1 and select the V0 point with subscript 0 in the figure to start traversing.
It is not difficult to see that the shortest path is selected starting from v0, that is, V0->V1, and then the selection traversal is performed, that is, V0->V1->V2, as shown in Figure 2.
By repeating this process, the shortest weight path from the source point V0 to the end point V8 can be obtained. As shown in Figure 3.
Implementation of Dijkstra’s algorithm
First of all, we need to know that Dijkstra’s algorithm is based on the adjacency matrix. If you are not familiar with the adjacency matrix, you can review it here. I review the adjacency matrix.
The previous graph structure is converted into an adjacency matrix as shown in Figure 4.
Macro definition
#include <stdio.h> #include <stdlib.h> #define INFINITY 65535 #defineMAXVEX 9 typedef int Patharc[MAXVEX]; //Array used to store shortest path subscripts typedef int ShortPathTable[MAXVEX];//Used to store the weight sum of the shortest path typedef char VertexType; //Vertex type typedef int EdgeType; //weight on edge
Premise function implementation
typedef struct
{<!-- -->
VertexType vexs[MAXVEX];//Vertex table
EdgeType arc[MAXVEX][MAXVEX];//adjacency matrix
int numVertexes, numEdges;//number of vertices and edges
}MGraph;
void CreateMGraph(MGraph* G)
{<!-- -->
int k, w;
char i, j;
printf("Enter the number of vertices and edges:\
");
scanf("%d%d", & amp;G->numVertexes, & amp;G->numEdges);
printf("Please enter vertex information:");
getchar();
for (i = 0; i < G->numVertexes; i + + )//Input vertex information separately
{<!-- -->
scanf("%c", & amp;G->vexs[i]);
getchar();
}
for (i = 0; i < G->numVertexes; i + + )
for (j = 0; j < G->numVertexes; j + + )
G->arc[i][j] = INFINITY; //Initialize the weights between all points to be infinite
for (k = 0; k < G->numEdges; k + + )
{<!-- -->
printf("Enter the subscript i, subscript j and weight w on edge (vi, vj):\
");
scanf("%d%d%d", & amp;i, & amp;j, & amp;w);
G->arc[i][j] = w;
G->arc[j][i] = G->arc[i][j];//Undirected graph, matrix symmetry
}
}
Dijkstra’s algorithm
void ShortestPath_Dijkstra(MGraph G, int V0, Patharc* P, ShortPathTable* D)
{<!-- -->
int v, w, k, min;
int final[MAXVEX]; //final[w]=1 means to find the shortest path from vertex V0 to Vw
for (v = 0; v < G.numVertexes; v + + )
{<!-- -->
final[v] = 0; //All vertices are initialized to the unknown shortest path state
(*D)[v] = G.arc[V0][v]; //Add weight to the vertices connected to the V0 point
(*P)[v] = 0; //Initialize path array P to 0
}
(*D)[V0] = 0; //The path from v0 to v0 is 0
final[V0] = 1; //No path required from v0 to v0
//Start the main loop and find the shortest path from v0 to a certain v vertex each time
for (v = 1; v < G.numVertexes; v + + )
{<!-- -->
min = INFINITY;
for (w = 0; w < G.numVertexes; w + + )
{<!-- -->
if (!final[w] & amp; & amp; (*D)[w] < min)
{<!-- -->
k = w;
min = (*D)[w]; //The vertex w is closer to v0
}
}
final[k] = 1; //Indicates that the vertex with subscript k is already in the path
for (w = 0; w < G.numVertexes; w + + )//check again
{<!-- -->
if (!final[w] & amp; & amp; (min + G.arc[k][w]<(*D)[w]))
{<!-- -->
(*D)[w] = min + G.arc[k][w];
(*P)[w] = k;
}
}
}
}
Main function implementation
int main()
{<!-- -->
MGraph G;
CreateMGraph( & amp;G);
Patharc P;
ShortPathTable D;
ShortestPath_Dijkstra(G,0, & amp;P, & amp;D);
}
Debugging results
1) The data of each subscript in the D array corresponds to the shortest weight to reach the vertex of this subscript.
2) The final array indicates whether each point in the array enters the shortest path.
3) The P array represents the previous vertex of each point in the array
Code analysis
Define an array to store the shortest path index
typedef int Patharc[MAXVEX]; Patharc P;
Define an array to store the shortest sum of weights
typedef int ShortPathTable[MAXVEX]; ShortPathTable D;
Define an array to determine whether a point has entered the shortest path, 1 means it has entered, 0 means it has not entered.
int final[MAXVEX];
Initialize various data for traversal.
for (v = 0; v < G.numVertexes; v + + )
{<!-- -->
final[v] = 0; //All vertices are initialized to the unknown shortest path state
(*D)[v] = G.arc[V0][v]; //Add weight to the vertices connected to the V0 point
(*P)[v] = 0; //Initialize path array P to 0
}
(*D)[V0] = 0; //The path from v0 to v0 is 0
final[V0] = 1; //No path required from v0 to v0
Perform the first traversal. Note that (*D)[] here is the first row of array data initialized before.
min = INFINITY;
for (w = 0; w < G.numVertexes; w + + )
{<!-- -->
if (!final[w] & amp; & amp; (*D)[w] < min)
{<!-- -->
k = w;
min = (*D)[w]; //The w vertex is closer to v0
}
}
final[k] = 1; //Indicates that the vertex with subscript k is already in the path
This can be done for the first traversal, but it cannot be done further down, so the following code completion is provided.
for (w = 0; w < G.numVertexes; w + + )//Check it again
{<!-- -->
if (!final[w] & amp; & amp; (min + G.arc[k][w]<(*D)[w]))
{<!-- -->
(*D)[w] = min + G.arc[k][w];
(*P)[w] = k;
}
}