Floyd-Warshall

原理

分别枚举起始点i，中转点k，目标点j
如果e[i][k]+e[k][j] < e[i][j]
更新e[i][j]的值

中转点枚举在最外层

模版

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100 
#define INF 0x7fffff
using namespace std;
int main()
{
	int g[N][N] = {};
	for(int i=0; i<=N; ++i)
		for(int j=0; j<=N; ++j)
			if(i != j)
				g[i][j] = INF;
			else
				g[i][j] = 0;
	int n, m;
	scanf("%d%d", &n, &m);
	int u, v, w;
	for(int i=0; i<m; ++i)
	{
		scanf("%d%d%d", &u, &v, &w);
		g[u][v] = w;
	}
	for(int k=1; k<=n; ++k)
		for(int i=1; i<=n; ++i)
			for(int j=1; j<=n; ++j)
				g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
	printf("%d", g[1][n]);
	return 0;
}

Dijkstra

原理

假设起点为1号节点

初始化1号节点的出边权值至dis数组（估计值）
找当前dis中最小边权（确定值）（假设为2号节点）
以2号节点的出边边权更新dis数组，若e[2][i]+dis[2] < dis[i]，就更新dis[i]
以此类推，进行松弛

每次找离源点最近的点，然后依次进行扩展
用book数组进行标记是否使用

模版

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100
#define INF 0x7ffff
using namespace std;
int main()
{
	int e[N][N], dis[N], book[N];
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; ++i)
		for(int j=1; j<=n; ++j)
			if(i == j)
				e[i][j] = 0;
			else
				e[i][j] = INF;
	int u, v, w;
	for(int i=1; i<=m; ++i)
	{
		scanf("%d%d%d", &u, &v, &w);
		e[u][v] = w;
	}
	for(int i=1; i<=n; ++i)
		dis[i] = e[1][i];
	memset(book, 0, sizeof(book));
	book[1] = 1;
	int minn = INF, k;
	for(int i=1; i<=n; ++i)
	{
		minn = INF;
		for(int j=1; j<=n; ++j)
			if(!book[j] && dis[j]<minn)
			{
				minn = dis[j];
				k = j;
			}
		book[k] = 1;
		for(int j=1; j<=n; ++j)
			if(e[k][j]<INF)
				dis[j] = min(dis[j], dis[k]+e[k][j]);
	}
	for(int i=1; i<=n; ++i)
		printf("%d ", dis[i]);
	return 0;
}

Bellman-Ford

原理

进行n-1轮松弛（详见Dijkstra）
没啥好说的

模版

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100
#define INF 0x7ffff
using namespace std;
int main()
{
	int dis[N], n, m, u[N], v[N], w[N];
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; ++i)
		scanf("%d%d%d", &u[i], &v[i], &w[i]);
	for(int i=1; i<=n; ++i)
		dis[i] = INF;
	dis[1] = 0;
	int check = 0;  //检查dis是否改变
	for(int i=1; i<=n-1; ++i)
	{
		check = 0;
		for(int j=1; j<=n; ++j)
			if(dis[v[j]] > dis[u[j]]+w[j])
			{
				dis[v[j]] = dis[u[j]]+w[j];
				check = 1;
			}
		if(!check)  //优化
			break;
	}
	int flag = 0;
	for(int i=1; i<=m; ++i)
		if(dis[v[i]] > dis[u[i]]+w[i])
			flag = 1;
	if(flag)
		printf("有负权回路");
	else
		for(int i=1; i<=n; ++i)
			printf("%d ", dis[i]);
	return 0;
}

SPFA

原理

用队列优化的Bellman-Ford
思想差不多（Bellman-Ford+BFS）
不用像BFS一样打标记（敲黑板）

不会邻接表的参考我的这篇博文

模版（邻接表）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100
#define INF 0x7ffff

using namespace std;
int main()
{
	int n, m;
	int u[N], v[N], w[N];
	scanf("%d%d", &n, &m);
	int first[n+1], next[m+1];
	int dis[N] = {}, book[N] = {}, que[N] = {}, head = 1, tail = 1;
	for(int i=1; i<=n; ++i)
		dis[i] = INF;
	dis[1] = 0;
	for(int i=1; i<=n; ++i)
		first[i] = -1;
	for(int i=1; i<=m; ++i)
	{
		scanf("%d%d%d", &u[i], &v[i], &w[i]);
		next[i] = first[u[i]];
		first[u[i]] = i;
	}
	que[tail++] = 1;
	book[1] = 1;
	int k;
	while(head < tail)
	{
		k = first[que[head]];
		while(k != -1)
		{
			if(dis[v[k]] > dis[u[k]]+w[k])
			{
				dis[v[k]] = dis[u[k]]+w[k];
				if(book[v[k]] == 0)
				{
					que[tail++] = v[k];
					book[v[k]] = 1;
				}
			}
			k = next[k];
		}
		book[que[head]] = 0;
		head++;
	}
	for(int i=1; i<=n; ++i)
		printf("%d ", dis[i]);
	return 0;
}

算法比较