JZTXT

最短路

发布时间 2023-09-05 13:44:36作者: 哈奇莱特

基本算法：

  1. \(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]) ;
}
  1. \(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]) ;
}