- yuxitong's blog
Dijkstra算法
- 2024-10-8 23:04:34 @
原理:
看这里
代码:
稠密图:邻接矩阵
//顶级垃圾程序
//A very bad program
#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int dist[N]; //dist[i]表示结点i到起点的距离
int g[N][N]; //g[i][j]表示结点i到结点j的边的长度
bool st[N]; //st[i]表示该结点是否确定了最小距离,1是确定,0是未确定
int n, m;
void Dijkstra(){
memset(dist, 0x3f, sizeof(dist)); //把距离初始化为正无穷
dist[1] = 0;
int iter = n;
while(iter--){ //n个点,循环n次
int t = -1;
//t随便初始化了一个不存在的结点,它最终用来存储未确定最小距离的结点,且该结点与其它结点相比目前到起点的距离最小
for(int i = 1; i <= n; i++)
if(st[i] == 0 && (t == -1 || dist[t] > dist[i]))
t = i;
st[t] = true;
//用结点t依次取更新其它结点到起点的距离,dist[i] = min(dist[i], dist[t] + g[t][i]);
for(int i = 1; i <= n; i++)
if(st[i] == 0)
dist[i] = min(dist[i], dist[t] + g[t][i]);
}
}
int main(){
cin >> n >> m;
memset(g, 0x3f, sizeof g);//将边先初始化为正无穷
while(m--){
int x, y, z;
cin >> x >> y >> z;
g[x][y] = min(g[x][y], z);//存在重边
//对于自环,不做处理,它不影响结果的计算
}
Dijkstra();
if(dist[n] == 0x3f3f3f3f)
cout << "-1" << endl;
else
cout << dist[n] << endl;
return 0;
}
稀疏图:用邻接表
//顶级垃圾程序
//A very bad program
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 1.5e5 + 10;
int st[N];
int head[N];
int dist[N];
int e[N], ne[N], w[N], idx;//用来存边
int n, m;
//边:a->b,权重为c
void add(int a, int b, int c){
e[idx] = b;
ne[idx] = head[a];
w[idx] = c;
head[a] = idx;
idx++;
}
void Dijkstra(){
//图的遍历
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});//first表示距离,second表示结点
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
while(heap.size()){
PII t = heap.top();
heap.pop();
int ver = t.second, d = t.first;
if(st[ver] == 1) continue;
st[ver] = 1;
//a->b, 已知a的距离和边权,去更新b的距离
for(int i = head[ver]; i != -1; i = ne[i]){
int j = e[i];
if(dist[j] > d + w[i]){
dist[j] = d + w[i];
heap.push({dist[j], j});
}
}
}
}
int main(){
cin >> n >> m;//n个结点, m条边
memset(head, -1, sizeof head);
while(m--){
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
}
Dijkstra();
if(dist[n] == 0x3f3f3f3f)
cout << -1 << endl;
else
cout << dist[n] << endl;
return 0;
}
样例输入:
3 3
1 2 2
2 3 1
1 3 4
样例输出:
3
解析: