最短路算法

_Cheems · 2023-08-02 22:07:35 · 个人记录

前言

本文意在介绍四种常用的最短路算法，并对不同情况下算法的选择进行分析。

不同算法的区别，在于时间复杂度以及负边、负环等的处理。

至于空间复杂度，影响不大。

前置知识

松弛操作

所有算法的底层原理都是松弛操作。

寻求 u 到 v 的最短路径时，不一定要直接得出，可以求出 u 至中间节点 k 的最短路，再递推得出答案。

若 k 与 v 直接相连，则松弛操作为：dis[v]=min(dis[v],dis[k]+e[k][v]);

负环、正环

负边：权值是负数的边。反之为正边（边长一定是正边）。

对于一个环，若其权值和为负数，则称之为负环，为正数就叫正环。

最短路径中不能存在负环或正环：

• 遇到负环，会无限绕圈，值是无限小的。

• 遇到正环，显然去掉环的一些边后可得到更小值，换言之这些边可有可无，反正最后会回到起始边。

最短路径的最优子结构

令 dis[x] 代表源点至 x 的最短路。

对于任意边 (x,y)，都存在 dis[y]=dis[x]+w(x,y)。

反过来也成立。若上式成立，则 (x,y) 为 u 至 v 最短路径上的一边。

几种算法

首先，我们定义 dis[i]：源点至 i 的最短路径长度。

Dijkstra

简介

单源最短路算法，时间复杂度 O(n^2)。

适用于正权边、稠密图。

将所有点分为：未确定最短路径的点集合 V 与已确定最短路径的点集合 S。

贪心的思路，每次选择最优点松弛其它点至源点的距离。正因如此，无法处理存在负边的情况。

算法流程

1. 初始化 dis 为极大数 \operatorname{INF}，并将源点加入 S 中。
2. 从每次从 V 中选取到 dis 值最小的点 u，将 u 插入 S，并松弛其出边指向之点。
3. 重复上一步 n-1 次。

若 dis[v] 仍为 \operatorname{INF}，则说明 u、v 不连通；否则答案即为 dis[v]。

堆优化

朴素做法的第二步耗费大量时间，考虑使用小根堆维护 S，做法如下：

1. 队列元素为 \operatorname{pair} 类型，前项即为最短距离，后项为节点编号。
2. 仿照朴素做法初始化，并把 u 加入堆。
3. 取出堆顶元素，若已在 S 中则弹出；否则加入 S，并松弛其出边指向之点 k_i。如果发现 dis[k_i] 松弛后更优，则将 k_i 加入堆。
4. 重复上一步直到堆为空。

可完全替代朴素做法，代码如下：

#define pir pair<long long,int>
void dj(int k){
    priority_queue<pir,vector<pir>,greater<pir>>q; //优先队列 
    memset(dis,0x7f7f7f,sizeof(dis)); 
    dis[k]=0; //初始化
    MAX=dis[0]; //极大数 
    q.push({0,k}); //将源点加入队列 
    while(!q.empty()){
        long long s=q.top().first;
        int k=q.top().second;
        q.pop();
        if(vis[k]){ //弹出重复点 
            continue;
        }
        vis[k]=1; 
        for(int i=head[k]; i;i=e[i].nxt){
            int j=e[i].v;
            if(!vis[j]&&dis[k]+e[i].w<dis[j]){ //将更新后更优点加入队列 
                dis[j]=dis[k]+e[i].w;
                q.push({dis[j],j});
            }
        }
    }
}

时间复杂度是 O(mlogn)，因此适用于稀疏图。

Bellman-ford

简介

单源最短路算法，时间复杂度 O(nm)。

可用于存在负边的情况，并能判断是否存在负环。

核心思想：对所有边松弛，操作 n-1 次即可。

算法流程

1. 遍历所有边，设每条边起点为 x_i，终点为 y_i，使用 dis[x_i] 松弛 dis[y_i]。
2. 重复上一步 n-1 次。

判断负环：操作完 n-1 次后，若还能松弛更新，则存在负环。

void Bf(int root){
    memset(dis,0x3f,sizeof(dis));
    MAX=dis[0];
    dis[root]=0;
    for(int i=1; i<=n-1;i++){
        for(int j=1; j<=cnt;j++){ //用邻接表存储，边为 1~cnt。 
            dis[e[j].v]=min(dis[e[j].v],dis[e[j].u]+e[j].w);
        }
    }
}

正确性简要证明

打代码时，不免产生疑惑：为啥运行 n-1 次后就一定能得出所有 dis ？

设最短路径为 v_1-v_2-...-v_n，最好情况当然是只运行 1 次，但事实上次序可能不同。

由于我们是遍历所有边，因此第 i 次时一定能得到 v_i-v_{i+1}，注意 i 是由 1 至 n-1 单调递增的。

于是遍历 n-1 次后，把它们串起来就一定能得到理想序列。

SPFA

简介

单源最短路算法，是 \operatorname{Bellman-ford} 的队列优化版，时间复杂度 O(km)。

参数 k 视情况而变，出题人可构造特殊数据（网格状）卡掉，当然平常刷题基本不会被卡。

算法流程

核心思想：只松驰可能有意义（更新后更优）的边。

1. 将起点加入队列。
2. 取出队头 k，松弛其出边 (k,v,w)。若松弛后 dis[v] 值更优，就将该 v 加入队列。
3. 统计每个点入队次数 d，若 d>n-1，就说明存在负环。
4. 重复执行上两步直到队列为空。

判断负环

第三步的作用是判断负环，容易被卡，因此最好使用其他方法：

较常用的方法：设 num 数组，当 v 被 u 松弛则令 num_v=num_u+1，num\ge n 则意味着有负环。

或是统计源点至所有点（不包含终点）的最短路径所包含的边数 cnt_i，若 cnt_i≥m 就代表存在负环。

玄学方法：在快要超时时直接结束算法，并认为存在负环。一般来说所有点入队次数超过 2n 时便可结束。当然不一定正确。

其它优化

SLF：优先考虑权值更优的点。若新加入的数优于队头元素，则入队头，否则入队尾。双向队列 \operatorname{deque} 实现。

LLL：大权值点推迟处理。若队头元素的权值大于全队平均值，则插入队尾，不断操作直到遇见反例。

只用一种提速二三成，双管齐下可快出五成。

Floyd

简介

多源最短路算法，时间复杂度 O(n^3)。短小精悍，还可用于连通性判断。

算法流程

1. 初始化数组，若存在边 (x,y,w)，则令 dis[x][y]=w。

2. 将路径用三点区分：起点 u、中转点 k、终点 v。

3. 依次枚举这三点，更新路径值： dis[u][v]=min(dis[u][v],dis[u][k]+dis[k][v]);

代码如下：

void floyd(){
    for(int k=1; k<=n;k++)
     for(int i=1; i<=n;i++)
      for(int j=1; j<=n;j++){
        dis[i][j]=dis[i][k]+dis[k][j]; 
    }
}

对比总结

能不用 \operatorname{SPFA} 就不用，它不稳定。