基本算法：
- \(dijkstra\)
使用条件：无负权边
每次取出 还未取出过的 \(dis\) 最小的节点更新其他节点
正确性证明：因为是\(dis\)最小的节点，别的节点不可能有一条路径走到这个节点且\(dis\)更小（路径为正）
stl-pq默认是大根堆，用负号处理为小根堆
int n, m, s, tot ;
int head[N], ver[M], edge[M], nxt[M] ;
int dis[N] ;
bool vis[N] ;
priority_queue <pair<int, int> > q ;
void add(int x, int y, int z) {
ver[++tot] = y ; edge[tot] = z ;
nxt[tot] = head[x] ; head[x] = tot ;
}
void dijkstra(int s) {
memset(dis, 0x3f, sizeof(dis)) ;
dis[s] = 0 ; q.push(make_pair(0, s)) ;
while (!q.empty()) {
int x = q.top().second ; q.pop() ;
if (vis[x]) continue ;
vis[x] = true ;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i], val = edge[i] ;
if (dis[y] > dis[x] + val) {
dis[y] = dis[x] + val ;
q.push(make_pair(-dis[y], y)) ;
}
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &s) ;
for (int i = 1; i <= m; i++) {
int x, y, z ; scanf("%d%d%d", &x, &y, &z) ;
add(x, y, z) ;
}
dijkstra(s) ;
for (int i = 1; i <= n; i++) printf("%d ", dis[i]) ;
}
- \(spfa\) 队列优化的\(bellman-ford\)
\(bellman-ford\):扫描每条边，如果\(dis[y]>dis[x]+edge\) 就更新,直到结束
spfa:每次扫描在队列里的节点
为了避免重复入队，设置\(v\)数组表示是否在队列中
int n, m, s, tot ;
int ver[M], nxt[M], edge[M], head[N] ;
int dis[N], v[N] ;
queue <int> q ;
void add(int x, int y, int z) {
ver[++tot] = y ; edge[tot] = z ;
nxt[tot] = head[x] ; head[x] = tot ;
}
void spfa(int s) {
memset(dis, 0x3f, sizeof(dis)) ;
dis[s] = 0 ; q.push(s) ;
while (!q.empty()) {
int x = q.front() ; q.pop() ;
v[x] = 0 ;
for (int i = head[x]; i; i = nxt[i]) {
int y = ver[i], val = edge[i] ;
if (dis[y] > dis[x] + val) {
dis[y] = dis[x] + val ;
if (!v[y]) v[y] = 1, q.push(y) ;
}
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &s) ;
for (int i = 1; i <= m; i++) {
int x, y, z ; scanf("%d%d%d", &x, &y, &z) ;
add(x, y, z) ;
}
spfa(s) ;
for (int i = 1; i <= n; i++) printf("%d ", dis[i]) ;
}