# The shortest path Dijkstra algorithm

Dijkstra algorithm is used to solve the shortest path problem, and its time complexity is o(n^2).

The general steps of the algorithm are as follows:
Set a vertex set, first add the source point to the set, then find a point closest to the far point, add it to the set, and use it to update the distance of all the points that can be reached by the source point that is not in the set and connected with it, and then continue this operation. After n-1 times, all the points will be updated.

Find the nearest point that the source point that is not in the collection can reach and join the collection:

```for(int j = 1; j <= poi_num; j++){
if(!vis[j] && Min > d[j]){
poi_temp = j;
Min = d[j];
}
}
vis[poi_temp] = 1;```

Use it to update the distance between the connected points that are not in the collection and the source points:

```for(int j = 1; j <= poi_num; j++){
if(!vis[j] && d[j] > d[poi_temp] + map[poi_temp][j]){
d[j] = d[poi_temp] + map[poi_temp][j];
}
}```

The complete code is as follows:

```#include <cstdio>
#include <iostream>
using namespace std;

const int Max = 0x3f3f3f3f;

bool vis;
int map;
int d;

void init(int n){
for(int i = 0; i <= n; i++){
d[i] = Max;
for(int j = 0; j <= n; j++){
map[i][j] = Max;
}
}
memset(vis, 0, sizeof(vis));
}

int main() {
int poi_n, edge_n, poi_bgn, poi_nd;
cin >> poi_n >> edge_n;
init(poi_n);
for (int i = 0; i < edge_n; i++) {
int poi_a, poi_b, len_c;
cin >> poi_a >> poi_b >> len_c;
map[poi_a][poi_b] = len_c;
map[poi_b][poi_a] = len_c;
}
cin >> poi_bgn >> poi_nd;
for (int i = 1; i <= poi_n; i++) {
d[i] = map[poi_bgn][i];
}
d[poi_bgn] = 0;
vis[poi_bgn] = 1;
for (int i = 1; i < poi_n; i++) {
int Min = Max;
int poi_temp;
for (int j = 1; j <= poi_n; j++) {
if (!vis[j] && d[j] < Min) {
poi_temp = j;
Min = d[j];
}
}
vis[poi_temp] = 1;
for (int j = 1; j <= poi_n; j++) {
if (!vis[j] && map[poi_temp][j] + Min < d[j]) {
d[j] = map[poi_temp][j] + Min;
}
}
}
cout << d[poi_nd] << endl;
return 0;
}```

Added by ss-mike on Thu, 30 Apr 2020 14:37:19 +0300