2025-09-29

最短路问题实战

当出现一个复杂度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; 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; }