「Day 5—最短路径」

最短路问题

单源最短路

全源最短路

Floyd算法

通过转移方程判断 i -> j 的路径中，是否有 i -> k -> j 更短，运用简单 dp 来转移状态。
f[i][j] 表示 i -> j 的最短路径长度。
但不要忘了初始化，一个点到其本身的最短路径为 1，即 f[i][i] = 1,其余的初始化为 '1e9' 即可。

for(int i = 1;i <= n;i ++){
	for(int j = 1;j <= n;j ++){
		if(i == j){
			f[i][j] = 0;
		}
		else f[i][j] = 1e9;
	}
}
for(int i = 1;i <= n;i ++){
	int u,v,w;
	cin >> u >> v >> w;
	f[u][v] = min(f[u][v],w);
	f[v][u] = min(f[v][u],w);
}
for(int k = 1;k <= n;k ++){
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= n;j ++){
			if(f[i][j] > f[i][k] + f[k][j]){
				f[i][j] = f[i][k] + f[k][j];
			}
		}
	}
}

单源最短路

SPFA

我们需要先知道一个前置知识：松弛操作。
那么什么是松弛操作呢，就是当 d[to] > d[v] + e[i].len 的时候，更新 d[to] 为 d[v] + e[i].len 即可。
那么 SPFA 的实现可以通过队列来实现，不断更新当前点所连的点，而每个点可能入队多次。
但 SPFA 容易被卡，所以一般是不用的，但是 SPFA 的最大作用是判负环，如果 cnt[to] + 1 > n 则说明其有负环。

#include<iostream>
#include<math.h>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

const int MAXN=1e4+5;
const long long INF=2147483647;
struct e {
	int v,w;
};
vector<e> G[MAXN];
queue<long long> q;
long long dis[MAXN],cnt[MAXN];
bool vis[MAXN];
long long n,m,s;

void SPFA() {
	for(int i=1;i<=n;i++){
		dis[i]=INF;
		vis[i]=0;
	}
	dis[s]=0,vis[s]=1;
	q.push(s);
	while(!q.empty()) {
		long long u=q.front();
		vis[u]=0;
		q.pop();
		for(auto edge:G[u]) {
			long long v=edge.v;
			long long w=edge.w;
			if(dis[v]>dis[u]+w) {
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n) return;
				if(!vis[v]) q.push(v);
				vis[v]=1;
			}
		}
	}
	return;
}

int main() {

	cin>>n>>m>>s;

	for(int i=1; i<=m; i++) {
		long long u,v,w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
	}

	SPFA();

	for(int i=1; i<=n; i++) {
		if(s==i) cout<<"0 ";
		else cout<<dis[i]<<" ";
	}

	return 0;
}

Dijkstra