前言与模板
需要读者对最短路之不含负权边：Dijkstra算法朴素和堆实现 有所了解。
1、bellman-ford
适用情况：
- 与拓展次数有关
- 可用于负权。因为有次数限制，所以可以有负环（负权回路）
简要介绍：
暴力法。每次大循环的含义是向外拓展一次，每次大循环将所有的边遍历一次。
模板：
//循环k次(拓展k次边) 每次循环尝试更新所有的节点最小值
int bellman_ford(int n, int m, int k) //n个节点 m条边 k次
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < k; ++ i)
{
memcpy(before, dist, sizeof dist); //大循环的含义是拓展一步，所以要用额外数组记录之前的数据，防止串联更新
for(int i = 0; i < m; ++ i)
{
int x = node[i].x, y = node[i].y, w = node[i].w;
dist[y] = min(dist[y], before[x] + w);
}
}
if(dist[n] > 0x3f3f3f3f / 2) return 0x3f3f3f3f; //可能有负边
return dist[n];
}2、spfa
适用情况：
- 边权可能有负数
- 不能有负环
简要介绍：
- 和 $ballman-ford$ 算法的关系就像是 $Dijkstra$ 堆版本和朴素版本。
- 用到了贪心策略：一个点的值想要被更新的前提是它的前驱更新了。所以我们只需要处理能更新数据的节点的后继。因为没有具体的拓展次数限制，用普通队列加上去重思想存储节点下标即可。
模板：
int spfa(int n)
{
memset(dist, 0x3f, sizeof dist);
queue<int> q;
q.push(1); dist[1] = 0; b[1] = true; //布尔数组用与存节点在不在队列中
while(q.size())
{
int t = q.front(); q.pop(); b[t] = false;
for(auto & i : a[t])
{
int newnode = i.first, val = i.second;
if(dist[newnode] > dist[t] + val)
{
dist[newnode] = dist[t] + val;
if(b[newnode]) continue; //预节点在队列中，不需要加入队列，但要更新数值
q.push(newnode);
b[newnode] = true;
}
}
}
return dist[n]; //从源点出发搜索，如果能被更新就一定有路
}3、Floyd
适用情况：
- 边权可能为负数
- 没有负权回路
- 多次查询任意两点之间的最短路径
简要介绍：
- 动态规划思想：令
dp[i, j, k]表示 $i$ 到 $j$ 只经过 $1$~$k$ 的点的答案。有 $dp$ 公式如下：dp[i, j, k] = min(dp[i, j, k - 1], dp[i, k, k - 1] + dp[k, j, k - 1])。发现 $k$ 与 $k - 1$ 的状态有关，所以最外层的循环是 $k$。 - 处理输入：自环都为 $0$，其它边赋值无穷大，输入时可能会出现重边、取最小值。
模板：
void floyd(int n)
{
for(int k = 1; k <= n; ++ k)
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}例题（点击题目跳转链接）
一、有边数限制的最短路
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径，则输出 impossible。
数据范围
1≤n,k≤500,1≤m≤10000,任意边长的绝对值不超过 10000。
输入样例：
3 3 1
1 2 1
2 3 1
1 3 3输出样例：
3题目分析
有强烈的次数限制，用 bellman-ford 暴力循环要求的次数即可
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 505, M = 1e4 + 5;
struct Node{
int x, y, w;
}node[M];
int dist[N], before[N];
int bellman_ford(int n, int m, int k) //n个节点 m条边 k次
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < k; ++ i)
{
memcpy(before, dist, sizeof dist); //大循环的含义是拓展一步，所以要用额外数组记录之前的数据
for(int i = 0; i < m; ++ i)
{
int x = node[i].x, y = node[i].y, w = node[i].w;
dist[y] = min(dist[y], before[x] + w);
}
}
if(dist[n] > 0x3f3f3f3f / 2) return 0x3f3f3f3f; //可能有负边
return dist[n];
}
int main()
{
ios::sync_with_stdio(false);
int n, m, k; cin >> n >> m >> k;
int a, b, c;
for(int i = 0; i < m; ++ i)
if(cin >> a >> b >> c)
node[i] = {a, b, c};
int t = bellman_ford(n, m, k);
if(t != 0x3f3f3f3f) cout << t;
else cout << "impossible";
return 0;
}二、spfa判断负环
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
如果图中存在负权回路，则输出 Yes，否则输出 No。
数据范围
1≤n≤2000,1≤m≤10000, 图中涉及边长绝对值均不超过 10000。
输入样例：
3 3
1 2 -1
2 3 4
3 1 -4输出样例：
Yes题目分析
spaf 算法用队列实现，当有负环时队列永远也不会为空，怎样判断有负环呢？这里用到的主要思想有：
- 抽屉原理：通过当前节点的最短路的路径大于等于总结点数时一定有环
- 集合思想：数组表示的是离开该节点时路径的总数。如果有节点
a->b那么cnt[b] = cnt[a] + 1
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
typedef pair<int, int> PII;
vector<vector<PII>> a;
int cnt[N], dist[N];
bool b[N];
bool spfa(int n)
{
//求的是负环，能更新的一定是负数，0已经是一个无穷大了。所以不用数组初始化
queue<int> q;
for(int i = 1; i <= n; ++ i) q.push(i), b[i] = true; //所有的点同时出发
while(q.size())
{
int t = q.front(); q.pop(); b[t] = false;
for(auto &i : a[t])
{
if(dist[i.first] > dist[t] + i.second)
{
dist[i.first] = dist[t] + i.second;
cnt[i.first] = cnt[t] + 1; //集合思想
if(cnt[i.first] >= n) return true; //抽屉原理
if(b[i.first]) continue;
b[i.first] = true;
q.push(i.first);
}
}
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
int n, m; cin >> n >> m;
a.resize(n + 1);
int x, y, z;
for(int i = 0; i < m; ++ i)
if(cin >> x >> y >> z)
a[x].push_back({y, z});
if(!spfa(n)) cout << "No";
else cout << "Yes";
return 0;
}三、牛的比赛
N 头奶牛，编号 1∼N，一起参加比赛。
奶牛的战斗力两两不同。
这些奶牛之间已经进行了 M 轮两两对决。
在对决中，战斗力高的奶牛一定会战胜战斗力低的奶牛。
请问，通过上述 M 轮对决的结果，可以确定多少头奶牛的具体战斗力排名。
输入格式
第一行包含两个整数 N,M。接下来 M 行，每行包含两个整数 a,b，表示奶牛 a 和奶牛 b 之间进行了对决，并且奶牛 a 战胜了奶牛 b。
输出格式
输出可以确定具体战斗力排名的奶牛数量。
数据范围
1≤N≤100,1≤M≤4500, 数据保证合法。
输入样例：
5 5
4 3
4 2
3 2
1 2
2 5输出样例：
2样例解释
2 号奶牛输给了 1,3,4 号奶牛，战胜了 5 号奶牛，可以确定它的战斗力排名为 4。5 号奶牛输给了排在第 4 的 2 号奶牛，所以它的战斗力排名为 5。其它奶牛不确定。
题目分析
可将 a 战胜 b 的关系看作a->b的有向图。经过某种算法之后遍历每一个点，如果该点和其它所有的点之间都有边连接的话：该点可以被排名。
那要用哪种算法呢？注意到我们分析里面包含了大量的查询操作，于是选择 $Floyd$ 算法。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
const int INF = 0x3f3f3f3f;
int a[N][N];
void floyd(int n)
{
for(int k = 1; k <= n; ++ k)
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= n; ++ j)
a[i][j] |= (a[i][k] && a[k][j]);
}
int main()
{
ios::sync_with_stdio(false);
int n, m; cin >> n >> m;
int x, y;
while(m --) if(cin >> x >> y) a[x][y] = 1; //x打败y 有向图
floyd(n);
int ans = 0;
for(int i = 1; i <= n; ++ i)
{
int tmp = 0;
for(int j = 1; j <= n; ++ j)
if(a[i][j] || a[j][i])
tmp ++;
if(tmp == n - 1)
ans ++;
}
cout << ans;
return 0;
}小结
- 有负权边在更新数据方面必须要有松弛操作
- bf 有强烈的次数意识；spfa 可以理解为 bf 的贪心版；floyd 涉及 dp 操作，数组存储信息，支持多次查询。