最短路算法总结
粥2414
·
2025-04-25 17:06:48
·
算法·理论
UPD：更正一些错误，并增加了对一些算法的说明。
UPD：对 Johnson 算法进行了补充。
最短路算法
最短路算法是一种用来求图上两点之间的最短距离的算法。主要分为单源最短路和全源最短路两种。
求单源最短路的算法主要有 Dijkstra 和 SPFA 两种，对于含有负边权的图，只可以用 SPFA 算法。
全源最短路可以通过跑 n 遍单源最短路求出，也可以用 Floyd 求出。
另外，johnson 算法用于将负权图转化为非负权图，同时保证任意两点间最短路径不变。通常在求全源最短路时使用。
接下来我会依次讲解一下这几种算法。
松弛操作
松弛是所有最短路算法都会用到的一个操作。设 dis_i 为点 1 到 i 的最短路，对于边 (u,v)，松弛操作对应为 dis_v=\min(dis_v,dis_u+w_{u,v})。显然这就是用一条边去更新最短路的操作。
单源最短路
为方便表述，称已经求出最短路的点为最短点。
Dijkstra
适用于非负边权。
可能是最常用的最短路算法，它十分好写，而且在非负边权的图中是效率最高的。
它的本质是贪心。初始时设除起始点外所有点的 dis 为 +\infty，然后从所有非最短点中找到一个 dis 最小的，将它标记为最短点，用它的边去松弛其他的点。循环往复。
贪心证明我不会，可以参考 oi-wiki。
对于存在负边权的情况，此算法就失效了。原因是贪心无法保证无后效性，可能会有某个负边导致当前选取到的点并非实际上距离最近的。可以很轻松地举出一个反例：
此时手动模拟可以发现 Dijkstra 算法是错误的。所以对于存在负边的图就只能用 SPFA 了。
朴素实现
void dj(ll s){
for(int i=0;i<=n;i++)dis[i]=INF;
dis[s]=0;
for(int k=1;k<=n;k++){//当前解决了k个点的最短路
ll minn=INF,id;
for(int i=1;i<=n;i++){//暴力查找
if(!bo[i]&&dis[i] minn=dis[i],id=i; } } bo[id]=1; for(int i=h[id];i;i=lian[i].ne){//松弛 if(dis[id]+lian[i].w } } } 其中 bo_i 表示点 i 是否为最短点，lian 为链式前向星。 显然这样的时间复杂度为 O(n^2+m)，在稠密图中复杂度比较优秀。但是如果在稀疏图中，那么其还有优化的空间。 优先队列（堆）优化 观察到只有被松弛过的点可能被选中。所以可以开一个小根堆维护被松弛过的点，每次只要从堆顶取一个点即可。如果采用不同的堆来维护，那么会得到不同的复杂度。其中较快的有斐波那契堆，复杂度为 O(n\log n+m)，而对于更常用的 STL 优先队列优化，复杂度为 O(m\log m)。 如果一个点在堆中而又被松弛成功，那么如果是手写堆，直接修改即可。如果用的是 STL，那么就只能再插入一次，取出时判断是否已经是最短点，如果是就跳过。 struct NODE{ ll id,dis; bool operator<(const NODE &b)const{ return dis>b.dis;//小根堆 } }; inline void dj(ll s){ memset(dis,0x3f,sizeof(dis)); dis[s]=0; priority_queue q.push({s,0}); while(!q.empty()){ ll now=q.top().id; q.pop(); if(bo[now])continue; bo[now]=1;//标记为最短点 for(int i=h[now];i;i=lian[i].ne){ ll to=lian[i].to; if(dis[to]>dis[now]+lian[i].w){//松弛 dis[to]=dis[now]+lian[i].w; q.push({to,dis[to]}); } } } } 总结 Dijkstra 的复杂度对比接下来要讲的 SPFA 来说是十分优秀的。但是它却无法正确处理存在负边权的情况。对于稀疏图，可以使用堆优化的版本，对于稠密图，则是朴素实现更优。 关于 SPFA 它死了。 但它还活着。 所谓 SPFA，其实就是队列优化的 Bellman–Ford 算法。朴素的 Bellman–Ford 算法太慢了，基本上没人写，所以就不讲了。 SPFA 在随机数据下跑得飞快，但只要出题人随手一卡，其复杂度就掉为了 O(nm)。但是对于存在负边权的图中，SPFA 是具有不可替代性的。如果没有特殊性质，那么可以放心使用 SPFA，不然这题将会不可做。 SPFA 算法的本质是 dp，看起来十分暴力，就是维护一个队列，每次取队首元素，然后枚举它的所有边进行松弛操作，将被松弛成功的点（若不在队中）加入队尾。循环往复，直到队列为空。这大概也是它容易被卡的原因。 SPFA 还可用于判断负环。容易发现在没有负环的情况下，一个点最多只会重复进队 n-1 次，即被所有点松弛一次。如果一个点进队了超过 n 次，那么则说明存在负环，这个点不存在最短路。 实现 inline bool SPFA(ll s) { for (int i = 1; i <= n; i++)dis[i] = 1e9; queue q.push(s); while (!q.empty()) { ll now = q.front(); q.pop(); cnt[now]++;//记录入队次数 if (cnt[now] > n)return 0;//存在负环 vis[now] = 0;//标记为不在队列中 for (int i = h[now]; i; i = lian[i].ne) { if (dis[now] + lian[i].w < dis[lian[i].to]) { dis[lian[i].to] = dis[now] + lian[i].w; if (!vis[lian[i].to])q.push(lian[i].to), vis[lian[i].to] = 1; } } } return 1;//不存在负环 } SPFA 还有许多优化方式，但是都不能显著优化时间且依然容易被卡，其中一些优化甚至有可能导致复杂度变为指数级，故不再赘述。 全源最短路 Floyd 最暴力的最短路。其本质是 dp。 首先维护一个邻接矩阵，表示两点间的最短路。然后三重循环，最外层循环枚举中间节点，内二层循环枚举起点与终点，暴力进行松弛操作。 这样做的本质是 dp，每次最外层循环枚举当前可以利用哪个点的边进行松弛，然后暴力枚举可能的起点终点进行松弛操作。在稠密图中求全源最短路时表现比较优秀。 时间复杂度 O(n^3)。 实现 inline void floyd(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i==j||j==k||i==k)continue; else dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } 注意对于未直接连边且不同的两点间的距离要赋为极大值。 Johnson 对于 n 较大且含有负边的稀疏图，跑 n 遍 SPFA 害怕被卡，想用 Dijkstra 怎么办？ Johnson 算法用于将负边权图转换为非负边权图，且保证任意两点间最短路不变，使得 Dijkstra 适用。但是由于其实现需要借助 SPFA，所以一般只在求全源最短路时才使用它。 其实现就是虚拟一个零号节点，向所有点建一个长度为 0 的有向边，然后跑一遍 SPFA。将有向边 (u,v) 的权值调整为 w_{u,v}+dis_u-dis_v。这样就可以将其权值转换为非负，且不影响最短路。 然后跑 n 遍 Dijkstra，设这样得到的 i,j 两点间最短路为 l_{i,j}，那么 l_{i,j}-dis_i+dis_j 便是答案。这么处理的原因在正确性证明里。 正确性证明 首先证明修改前后的最短路不变。 考虑每一条从 s 到 t 的路径的权值和： (w_{s,p_1}+dis_s-dis_{p_1})+(w_{p_1,p_2}+dis_{p_1}-dis_{p_2})+\cdots+(w_{p_x,t}+dis_{p_x}-dis_t)\\ =dis_s-dis_t+(w_{s,p_1}+w_{p_1,p_2}+\cdots+w_{p_x,t}) 可以发现括号内是各个路径的原本长度，而 dis_s-dis_t 是一个定值。所以各个路径之间的相对大小不变，也就是最短路不变。这同时也解释了如此处理答案的原因。 然后证明如此处理边权后为非负数。 首先对于任意一条有向边 (u,v)，有 dis_u+w(u,v)\geq dis_v。 简单证明：首先可以发现点 v 的最短路要么经过边 (u,v)，要么不经过它。对于第一种情况，显然有 dis_u+w(u,v)= dis_v；对于第二种情况，一定存在一个路径比第一种情况中的路径短，否则最短路取情况一，所以有 dis_u+w(u,v)> dis_v。合在一起即可得上式。证毕。 那么移项即可推出 w(u,v)+dis_u-dis_v\geq 0。 证毕。 实现 inline void johnson(){ for (int i = 1; i <= n; i++)add(0, i, 0), dis[i] = 1e9;//虚拟节点 if (!SPFA(0))//存在负环 write(-1, 1); else { for (int i = 1; i <= n; i++) { for (int j = h[i]; j; j = lian[j].ne) lian[j].w += dis[i] - dis[lian[j].to]; }转换边权 for (int i = 1; i <= n; i++) {做n遍Dijkstra dj(i); } } } 如果使用堆优化的 Dijkstra，那么其时间复杂度为 O(nm\log m)。 例题 B3647 【模板】Floyd。 P3371 【模板】单源最短路径（弱化版）。 P4779 【模板】单源最短路径（标准版）。 P5905 【模板】全源最短路（Johnson）。