不会链式前向星的看这里

BF

BF 是 Dijkstra 的老祖宗。

BF 就是暴力搜所有边，找出最短路径树

BF 用到了三角不等式，就是说如果 $dis[v] <= dis[u] + w_{u,v}$，那么 dis 存的就是起点到 v 的最短距离。例子：

SPFA 是 BF 的队列优化，自行理解

代码（BF）

#include <bits/stdc++.h>
using namespace std;
const int N = 10005,M = 500005,INF = 1073741823;

// 链式前向星
struct edge{
	int u,v,w,prev;
}edges[M];
int tail[N],tot;
void add_edge(int u,int v,int w){
	edges[++tot] = {u,v,w,NULL};
	edges[tot].prev = tail[u];
	tail[u] = tot;
}

int dis[N],n,m,s;
void bf(){
	for (int i = 1;i < n;i++){
		bool f = 1;
		for (int j = 1;j <= m;j++){	// 注意：要遍历所有边，而不只是临边
			int u = edges[j].u,v = edges[j].v,w = edges[j].w;
			if (dis[u] + w < dis[v]){
				dis[v] = dis[u] + w;
				f = 0;
			}
		}
		if (f)	return;	// 所有边都满足了三角不等式，直接退出
	}
}
int main(int argc, char **argv){
	fill(dis,dis + N,INF);
	cin >> n >> m >> s;
	dis[s] = 0;
	for (int i = 0;i < m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		add_edge(u,v,w);
	}
	bf();
	for (int i = 1;i <= n;i++){
		if (dis[i] == INF)	printf("%d ",0x7fffffff);
		else	printf("%d ",dis[i]);
	}
	return 0;
}

代码（SPFA）

#include <bits/stdc++.h>
using namespace std;
const int N = 10005,M = 500005,INF = 1073741823;

// 链式前向星
struct edge{
	int u,v,w,prev;
}edges[M];
int tail[N],tot;
void add_edge(int u,int v,int w){
	edges[++tot] = {u,v,w,tail[u]};
	tail[u] = tot;
}

int dis[N],n,m,s;
bool f[N];
void bf(){
	queue<int> q;
	q.push(s);
	while (!q.empty()){
		int u = q.front();
		q.pop();
		f[u] = 0;
		for (int j = tail[u];j;j = edges[j].prev){
			int v = edges[j].v,w = edges[j].w;
			if (dis[u] + w < dis[v]){
				dis[v] = dis[u] + w;
				if (!f[v])	q.push(v),f[v] = 1;
			}
		}
	}
}
int main(int argc, char **argv){
	fill(dis,dis + N,INF);
	cin >> n >> m >> s;
	dis[s] = 0;
	for (int i = 0;i < m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		add_edge(u,v,w);
	}
	bf();
	for (int i = 1;i <= n;i++){
		if (dis[i] == INF)	printf("%d ",0x7fffffff);
		else	printf("%d ",dis[i]);
	}
	return 0;
}