最短路问题实战
当出现一个复杂度ok，可以直接套用最短路算法处理的问题时，是否经历过：想不起来，不知道如何选择Floyd，SPFA，Dijkstra？这篇文章会根据OI wiki的介绍全面覆盖这几个算法以及最简单的实现描述，并且结合更加具体的题目描述。
Floyd算法——最直白的算法
for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[k][x][y] = min(f[k - 1][x][y], f[k - 1][x][k] + f[k - 1][k][y]);
}
}
}即使用每一个路径点来更新路径的最短长度
但是有一些空间上的优化之处，由于每次更新k时，k-1都已经完成计算且没有后续作用，所以可以消去第一维度
for (k = 1; k <= n; k++) {
for (x = 1; x <= n; x++) {
for (y = 1; y <= n; y++) {
f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
}
}
}由于时间复杂度较高，因此在大部分有要求的题目中都会被卡（），不过通过这个办法可以求出所有的最短路径，并且在正负边权，有向无向图中都适用。（不能有负环）
Bellman–Ford 算法
这是一种基于松弛（relax）操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进行判断。复杂度优于floyd
对于一个边(u,v)，松弛操作即为：dis(v) = min(dis(v),dis(u)+(u,v))
即尝试使用S->u->v去更新到v点的最短路的长度，如果路径更优，就进行更新。
在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 +1，而最短路的边数最多为 𝑛 −1，因此整个算法最多执行 𝑛 −1 轮松弛操作。故总时间复杂度为 𝑂(𝑛𝑚)。
所以如果当n轮的时候，仍然可以对边进行松弛，那么说明从S出发可以抵达一个负环，这是有问题的
struct Edge {
int u, v, w;
};
vector<Edge> edge;
int dis[MAXN], u, v, w;
constexpr int INF = 0x3f3f3f3f;
bool bellmanford(int n, int s) {
memset(dis, 0x3f, (n + 1) * sizeof(int));
dis[s] = 0;
bool flag = false; // 判断一轮循环过程中是否发生松弛操作
for (int i = 1; i <= n; i++) {
flag = false;
for (int j = 0; j < edge.size(); j++) {
u = edge[j].u, v = edge[j].v, w = edge[j].w;
if (dis[u] == INF) continue;
// 无穷大与常数加减仍然为无穷大
// 因此最短路长度为 INF 的点引出的边不可能发生松弛操作
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
flag = true;
}
}
// 没有可以松弛的边时就停止算法
if (!flag) {
break;
}
}
// 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环
return flag;
}