最短路算法总结

zhou2414 · 2025-04-25 17:06:48 · 算法·理论

最短路算法

最短路算法是一种用来求图上两点之间的最短距离的算法。主要分为单源最短路和全源最短路两种。求单源最短路的算法主要有 Dijkstra 和 SPFA 两种，对于含有负边权的图，只可以用 SPFA 算法。全源最短路可以通过跑 n 遍单源最短路求出，也可以用 Floyd 求出。接下来我会依次讲解一下这几种算法。

松弛操作

松弛是所有最短路算法都会用到的一个操作。设 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){
                minn=dis[i],id=i;
            }
        }
        bo[id]=1;
        for(int i=h[id];i;i=lian[i].ne){//松弛
            if(dis[id]+lian[i].w<dis[lian[i].to])dis[lian[i].to]=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<NODE>q;
    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 算法看起来十分暴力，就是维护一个队列，每次取队首元素，然后枚举它的所有边进行松弛操作，将被松弛成功的点（若不在队中）加入队尾。循环往复，直到队列为空。这大概也是它容易被卡的原因。

SPFA 还可用于判断负环。容易发现在没有负环的情况下，一个点最多只会重复进队 n-1 次，即被所有点松弛一次。如果一个点进队了超过 n 次，那么则说明存在负环，这个点不存在最短路。

实现

inline bool SPFA(ll s) {
    for (int i = 1; i <= n; i++)dis[i] = 1e9;
    queue<ll>q;
    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，每次最外层循环枚举当前可以利用哪个点的边进行松弛，然后暴力枚举可能的起点终点进行松弛操作。在稠密图中求全源最短路时表现比较优秀。

时间复杂度 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。这样就可以将其权值转换为非负，且不影响最短路。

其正确性证明可以看 oi-wiki。

实现

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）。