“This is the 10th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.
Introduction of algorithm
Dijkstra algorithm is the shortest path algorithm in graph theory. It can solve the shortest path from a specific starting point to any point. For a graph with NNN vertices, the dijkstra algorithm is run NNN times if the shortest path between every two points is to be solved.
The time complexity of Dijkstra is O(n2)O(n^2)O(n2), but it is not suitable for graphs with negative weights.
Algorithm thought
Dijkstra algorithm, based on the greedy idea, constantly seeks intermediate node WWW so that the distance of U → W →vu\to W → W →v is less than that of U → VU \to vu→v, and updates the results with intermediate values. The idea of similarity algorithm refers to the adjacency matrix method of Pusu Dijkstra algorithm.
Pusu Dijkstra algorithm
Adjacency matrix method
Map [I][j]map[I][j]map[I][j]map[I][j]map[I][j]map[I][j]map[I][j]map map[I]=0map[I][I]=0map[I][I]=0map[I][I]=0 If iii to JJJ no edge map [I] [j] = up map [j] = \ [I] infinmap [I] [j] = up.
For a graph with the number of vertices NNN, if the shortest path length from point XXX to any point is found, Dijkktra maintains an array dist[]dist[]dist[] dist[] Dist [] Dist [y]dist[y] represents the shortest path length from XXX to YYy. Secondly, a visit[]visit[]visit[] array of length NNN is maintained. Visit [j]visit[j]visit[j] visit[j] indicates whether JJJ has been accessed.
- Dist []dist[]dist[] is ∞\infin∞, indicating that the distance from XXX to any point is infinite. Dist [x]=0dist[x]=0dist[x]=0, indicating that the distance from XXX to itself is 000. Initialize visit[]visit[]visit[] If the array value is 000, the visit point is not accessed. Go to Step 222.
- Dist [j]dist[j]dist[j] dist[j]dist[j]dist[j] dist[j] =1.
- Update the path with JJJ to see if the path with JJJ as the intermediate node is shorter than the known path, or update if the path is shorter. Dist [y] = min (dist [y], dist [j] + map [j] [y]) dist [y] = min (dist [y], dist [j] + map [j] [y]) dist [y] = min (dist [y], dist [j] + map [j] [y]), Go back to step 222 until all vertices are accessed.
void Dijkstra(int x){// Find x at any point
memset(dist,INF,sizeof(dist));//dist[]=INF
dist[x]=0;
memset(visit,0.sizeof(visit));
for(int i=1; i<=n; i++){int j=0;
for(int k=1; k<=n; k++){// Find the minimum dist not accessed [j]
if(! visit[k]&&dist[k]<=dist[j]){ j=k; } } visit[j]=1;
for(int k=1; k<=n; k++){/ / update the dist [j].
dist[k]=min(dist[k],dist[j]+map[j][k]); }}}Copy the codeAdjacency list method
In addition to the adjacency matrix, the Dijkstra algorithm can also be rewritten as an adjacency list. The chain forward star structure is adopted here. In fact, the so-called chain forward star is a linked list realized by array simulation, that is, a static linked list. Head []head[] Head [] Array represents an array of vertices, pointing to subscripts of edges connected to vertices. To [k]to[k]to[k] array represents the pointing vertex number of the KKK edge, val[k]val[k] represents the weight of the KKK edge.
void Dijkstra(int x){// Find x at any point
memset(dist,INF,sizeof(dist));//dist[]=INF
dist[x]=0;
memset(visit,0.sizeof(visit));
for(int i=1; i<=n; i++){int j=0;
for(int k=1; k<=n; k++){// Find the minimum dist not accessed [j]
if(! visit[k]&&dist[k]<=dist[j]){ j=k; } } visit[j]=1;
for(intk=head[j]; k; k=next[k]){/ / update the dist [j].
dist[to[k]]=min(dist[to[k]],dist[j]+val[k]); }}}Copy the codeHeap optimization Dijkstra algorithm
- The optimizable point of Pusudijstra algorithm is to find the unvisited vertex JJJ satisfying minimum Dist [j]dist[j]dist[j] dist[j]. This process can adopt heap optimization, which is called priority queue.
Algorithm thought
Dist []=INFdist[]=INFdist[]=INF, except dist[x]=0dist[x]=0dist[x]=0. Then we take the smallest distance of the intermediate node JJJ out of the heap each time, Will be able to update all the dist [j] + map [j] [k] < dist [k] dist [j] + map [j] [k] < dist [k] dist [j] + map [j] [k] < dist [k] dist [k] dist [k] dist update for [k] Dist [j]+map[j][k]dist[j]+map[j][k]dist[j]+map[j] +map[j][k]dist[J]+map[j][k]
prompt
-
pair
pair
pair
Since PairPAirPair defaults to sorting by typeAtypeAtypeA, typeAtypeAtypeA should be the distance and typeBtypeBtypeB is the node number.
- C++ c++ priority_queuepriority\_queuepriority_queue defaults to the big top heap, so you need to overload the comparison operator.
- Priority_queuepriority \_queuepriority_queue is located in
and pairpairpair is located in < Utility >< Utility >.
Adjacency matrix method
void Dijkstra(int x){// Find x at any point
memset(dist,INF,sizeof(dist));// Initialize the farthest distance
typedef pair<int.int> pr;// Store distance and vertex number respectively
priority_queue<pr,vector<pr>,greater<pr> > Q;// Priority queue, overload operator
dist[x]=0;// Initialize the source distance to 0
Q.push(make_pair(0,x));
while(! Q.empty()) {int j=Q.top().second;
Q.pop(a);if(visit[j]) continue;
visit[j]=1;
for(int k=1; k<=n; k++){/ / update the dist [j].
if(dist[j]+map[j][k]<dist[k]){
dist[k]=dist[j]+map[j][k];
if(! visit[k]) Q.push(make_pair(dist[k],k)); }}}}Copy the codeAdjacency list method
Similarly, heap optimization can also use the chain forward star structure, the detailed array meaning refer to the adjacency list method of the naive algorithm.
void Dijkstra(int x){// Find x at any point
memset(dist,INF,sizeof(dist));// Initialize the farthest distance
typedef pair<int.int> pr;// Store distance and vertex number respectively
priority_queue<pr,vector<pr>,greater<pr> > Q;// Priority queue, overload operator
dist[x]=0;// Initialize the source distance to 0
Q.push(make_pair(0,x));
while(! Q.empty()) {int j=Q.top().second;
Q.pop(a);if(visit[j]) continue;
visit[j]=1;
for(intk=head[j]; k; k=last[k]){/ / update the dist [j].
if(dist[j]+val[k]<dist[to[k]]){
dist[to[k]]=dist[j]+val[k];
if(! visit[to[k]) Q.push(make_pair(dist[to[k]],to[k])); }}}}Copy the codeconclusion
The efficiency of dijkstra algorithm after heap optimization is higher than that of SPFASPFASPFA algorithm, but it cannot be applied to graphs with negative weights. The efficiency of Dijkstra algorithm is higher than that of naive algorithm in time complexity, and the adjacency list algorithm is better than that of adjacency matrix algorithm in space complexity.