最短路问题

Published: January 20, 2021 by Daltao

• Categories:
• algorithm 101

• Tags:

• 最短路算法
  • BFS算法
  • 01权重BFS算法
  • 单源最短路算法：Dijkstra算法
  • 单源最短路算法：Bellman-Ford算法
  • 单源最短路算法：Spfa算法
  • 全源最短路算法：Floyd-Warshall
  • 全源最短路算法：Johnson
  • 带修改的最短路问题
• 循环依赖等式计算

最短路算法

一些记号：

• $G$: 图
• $V$: 顶点集合（在公式中表示顶点数目）
• $E$: 边集（在公式中表示边数目）
• $(u,v)$: 从$u$到$v$的边
• $W(u,v)$: 边$(u,v)$的权重
• $D(u)$: 从源点到$u$的最短距离
• $L(u)$: 从源点到$u$的最短路径的拥有的边数（长度）

BFS算法

BFS算法适用于这样一类图，所有的边的权重恰好都是1。BFS算法的时间复杂度为$O(V+E)$。

BFS算法非常简单，我们需要维护一个先进先出的队列，一开始将除了源点外所有顶点的距离设为无穷，而将源点的距离设为0。之后我们将源点加入到队列中，重复下面过程直到队列为空：

1. 弹出队列头部顶点，记作$u$。
2. 遍历$u$的所有出边$(u,v)$，如果$D(v)>D(u)+1$，那么就令$D(v)=D(u)+1$，并且将$v$加入到队列尾部。

BFS算法实际上会先找到最短路径为0的所有顶点，之后是为1的，之后为2的，如是循环。很显然，由于在加入$v$的时候，所有最短距离小于$D(u)$的顶点都已经被处理了，因此可以保证之后$v$的距离都不会再变化，因此每个顶点恰好被入队以及处理一次，总的时间复杂度为$O(V+E)$。

01权重BFS算法

BFS算法除了可以解决所有边权为1的图的最短路，还能解决所有边权为0或1的图的最短路问题。

非常简单，BFS的原理是一个简化版本的Dijkstra算法，我们用维护一个距离递增的队列来存储顶点。而实际上维护这样一个队列，是可以允许边为0的。考虑现在处理的队列前端元素为$v$，那么很显然弹出$v$后，队列中的所有元素距离都不小于$D(v)$。这样假如存在一条$0$权重边$(v,u)$，那么我们得到了$u$的距离也是为$D(v)$，这意味着将$u$加入到队列前端也不会影响队列中顶点距离递增的性质。因此我们这也就可以直接支持0或1边权的图了。

单源最短路算法：Dijkstra算法

Dijkstra算法要求图中的所有边权非负，它的时间复杂度为$O(\min(V^2+E,(V+E)\log_2V))$。

Dijkstra算法基于贪心算法，同样我们需要一开始将除了源点外所有顶点的距离设为无穷，而将源点的距离设为0。之后我们重复下面操作直到所有顶点都被处理过了：

1. 找到所有未处理的顶点中最短距离最小的那个顶点$u$。
2. 将$u$标记为处理过
3. 遍历所有$u$的出边$(u,v)$，如果$D(v)>D(u)+W(u,v)$，那么就令$D(v)=D(u)+W(u,v)$。

很显然上面的算法时间复杂度为$O(V^2+E)$。如果我们采用小根堆来存储顶点，那么时间复杂度就变成了$O(V+E)\log_2V)$。

下面证明一下Dijkstra算法的正确性。我们证明两点：

1. 被处理过的顶点$x$按照处理顺序，其处理时标记的距离$tag(x)$非严格递增。
2. 每个顶点$x$被处理的时候，其标记的距离$tag(x)$就是真正的最短距离$D(x)$。

第一点证明可以通过归纳法，很显然第一个处理的顶点是起点，其标记的距离为$0$，就是最短距离。之后考虑第一个被处理的顶点$v$，满足$tag(v)<tag(u)$，其中$u$在$v$之前被处理。那么由于$v$是第一个这样的顶点，因此$v$的前驱顶点$p$一定满足$tag(p)\leq tag(v)<tag(u)$，即$p$应该在$u$之前处理。而此时在$u$处理之前就有$tag(u)>tag(v)$了，因此$u$不可能在$v$之前处理，这里出现矛盾，因此第一点得到证明。

考虑第二点，同样通过归纳法进行证明。第一个被处理的点为起点$s$，因此$tag(s)=D(s)=0$。假设从$s$到$v$的最短路中除了$v$外其余顶点都满足标记距离等于最短距离。如果有$tag(v)>D(v)$，那么说明$v$一定在其前驱$p$处理之前被处理，考虑到$tag(v)>D(v)\geq D(p)=tag(p)$，根据第一点我们知道$v$一定在$p$之后处理，这里产生矛盾，因此第二点得到证明。

Dijkstra算法实际上使用了一个非常简单的贪心算法解决了无负权边情况下的最短路问题。它实际上还有很多优化的手段，比如用配对堆可以将时间复杂度优化到$O(V\log_2V+\alpha E)$，其中$\alpha$可以视作一个非常小的常数。因此对于顶点数比较少，但是边数非常多的情况也是可以适用的。还有一种特殊情况就是距离起点最远的顶点的距离为$D$的时候，还存在一个时间复杂度为$O(V+E+D)$的变种，具体就是维护$D+1$个普通队列，之后按照编号从小到大处理每一个队列，距离为$d$的顶点则放在第$d$个队列中。

单源最短路算法：Bellman-Ford算法

BM算法允许负权边，并且可以判断图中是否有负权环，它的时间复杂度为$O(V(V+E))$。

BF引入了松弛的概念，非常简单就是选一组顶点，遍历它们的出边，然后尝试优化入点的最短距离，比如说考虑顶点$u$，如果存在出$(u,v)$且$D(v)>D(u)+W(u,v)$，那么就将$D(u)$修改为$D(u)+W(u,v)$。

由于有负权边存在，因此Dijkstra采用的贪心策略是不能保证正确性的。但是我们可以发现在图上选择所有顶点跑一次松弛后尽管大部分顶点的最短距离是错误（大于真实的最短距离）的，但是对于$L(u)=1$的顶点$u$，它的最短距离是此时正确的。同理，当我们跑$k$次BFS后，所有满足$L(u)\leq k$的顶点$u$的最短距离都是正确的。

因此当图中不存在负权环的时候，由于对于任意顶点$u$满足$L(u)<V$，因此我们只需要在原图上选择所有顶点跑最多$V-1$次松弛即可。

当图中存在负权环的时候，那么我们在跑完$V$次BFS后如果有顶点的$L(u,v)$被标记为$V$，那么就一定存在了负权环。

无论是否存在负权环，时间复杂度的上界都是$O(V(V+E))$。

单源最短路算法：Spfa算法

Spfa的全称是Shortest path faster algorithm，我们可以将其理解为BF算法的优化版本（但是并没有优化时间复杂度的上界）。

考虑BF算法，我们发现如果某个顶点在上一次的BFS的最短距离没有变动，那么在下一次的BFS的时候就没必要将其作为源点加入。

Spfa算法的优化就是这么简单，其具体实现就是维护一个先进先出的队列，如果一个顶点的最短距离被修改了就入队。循环直到队列为空，或者某个顶点$u$的$L(u)\geq V$，前者无负环，后者表示出现了负环。

在不存在负环的时候Spfa一般会比BF算法快一点，但是有负环的时候两者相差不大。

全源最短路算法：Floyd-Warshall

FW算法可以用于计算图中每个点对的最短距离，FW允许负权边，但是不允许存在负权环。

我们用动态规划来计算所有点对的最短距离。由于s与t的最短距离必定会对应至少一条最短路径s..t，而s..t中除了两个端点外序号最大的点记为M(s..t)，称为路径的最大点。利用函数M，我们可以将图中所有路径分类为n种，第i类路径，其最大点为i。

FW算法的原理就是按分类从小到大处理所有路径，并利用这些路径计算得到所有点对之间的最短距离。记D(i,j,k)表示所有从i到j的前k类路径中最短的路径长度。对于D(i,j,k+1)，很显然i与j之间的最短路要么是前k类路，要么就是第k+1类路。如果是第k+1类路，这条路中的最大点为k+1，将路以k+1为断点分裂为两条，i..k+1，k+1..j，很显然两条路都是前k类路。因此：

$$D(i,j,k+1)=\min(D(i,j,k), D(i,k+1,k)+D(k+1,j,k))$$

之后动态规划，$O(n^3)$可以解决。

for(k = 1; k <= n; k++){
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){
            D[i][j] = min(D[i][j], D[i][k]] + D[k][j]);
        }
    }
}

全源最短路算法：Johnson

这个算法允许图中出现负权边，但是不允许图中出现负权环。它的时间复杂度为$O(\min(VE\log_2V, V^3))$，在图比较稀疏的时候会优于Floyd算法。

我们知道在没有负权边的时候，可以将每个顶点作为源点跑一次Dijkstra算法，这样的时间复杂度为$O(\min(VE\log_2V, V^3))$，那么在有负权的边的时候，能不能也用Dijkstra算法呢？Johnson算法就解决了这个问题。

首先我们向图中加入一个新的顶点，并从新的顶点到所有其它顶点建立一条权重为$0$的有向边，之后我们计算以新顶点作为源点的单源最短路（由于图中有负权边，所以使用BF算法）。

现在我们得到了每个顶点的最短距离，现在我们对所有图中原本存在的边的边的边权进行修正，考虑边$(u,v)$，我们将其新的边权设置为$W(u,v)+D(u)-D(v)$，由最短路性质我们知道$D(u)+W(u,v)\geq D(v)$，因此我们可以得知所有边的新的边权一定非负。

现在考虑一条路径$v_1,v_2,\ldots, v_k$，它的修正后的距离为

$$\begin{aligned} &W'(v_1,v_2)+W'(v_2,v_3)+\ldots +W'(v_{k-1},v_k)\\ =&W(v_1,v_2)+D(v_1)-D(v_2)+\ldots +W(v_{k-1},v_k)+D(v_{k-1})-D(v_k)\\ =&W(v_1,v_2)+W(v_2,v_3)+\ldots +W(v_{k-1},v_k)+D(v_1)-D(v_k) \end{aligned}$$

而$D(v_1)$和$D(v_k)$是已知的常数，因此我们可以保证在边权修正之前和修正之后两点之间的最短路是同一条。因此现在的问题就变成了在一个所有边权非负的图上找最短路。

带修改的最短路问题

题目1：给定$n$个顶点$m$条带权边（权重非负）的无向连通图，以及一个指定的顶点作为起点。之后$q$个请求。第$i$个请求分两类，第一类查询从起点到某个顶点$x_i$的距离，第二类增大$c_i$条边的权重，增大的总和不超过$M=10^5$。其中$1\leq n,m\leq 10^5$，$1\leq q\leq 10^3$。

很显然我们可以每次修改完成后都跑Dijkstra重新计算距离，这样时间复杂度为$O(q(n+m)\log_2n)$。有点大，但是可以用另外一个技巧将其中的$\log n$去掉。

具体的做法就是我们可以用类似Johnson算法的技术，先得出每个顶点到起点的最短路径，记第$i$个顶点的最短距离为$D_i$。之后我们修正每条边的权重为$w'(u,v)=D(u)+w(u,v)-D(v)$。由于最短路保证了$D(u)+w(u,v)\geq D(v)$，因此每条边修正后的权重还都是正数。类似于Jonnson算法，原图最短路也对应新图的最短路，因此我们可以通过在新图计算最短路就可以找到原图的最短路。

下面说这样做的好处是啥。在新图中，每个顶点到起点的最短路距离都是$0$。这是一个有用的性质，接下来考虑到所有边全权重增大的上限为$M$，因此我们可以保证新图修改过边权重后，所有顶点的最短距离均不会超过$M$。因此我们可以用Dijkstra一节中提到的优化技巧，不维护有限队列，转而维护$M$个普通队列，并按照编号从小到大进行处理，这样每次修改请求的时间复杂度就降低到了$O(M+n+m)$，而查询请求为$O(1)$。总的时间复杂度为$O(q(M+n+m))$。

一道题目。

题目2：给定$n$个顶点$m$条无向带权边构成的连通图，指定起点和终点。之后$q$个请求，第$i$请求询问，假如加入一条新的权重为$w_i$的新边$(u_i,v_i)$，要求回答起点到终点的最短距离（注意每个请求不会对之后的请求产生影响）。其中$1\leq n,m,q\leq 10^6$

很显然最短距离不会增加，但是有可能减少，减少仅发生在新的最短路一定经过$(u_i,v_i)$的情况下。如果我们预先用Dijkstra算法求出每个顶点到起点和终点的最短距离，那么每个请求都可以$O(1)$回答了。

时间复杂度为$O((m+n)\log_2n+q)$。

题目3：给定$n$个顶点$m$条无向带权边构成的连通图，指定起点和终点。之后$q$个请求，第$i$请求询问，假如删除原本编号为$e_i$的边，要求回答起点到终点的最短距离或者报告不连通（注意每个请求不会对之后的请求产生影响）。其中$1\leq n,m,q\leq 10^6$，且每条边的权重为$1$到$10^9$之间

我们可以通过tarjan算法将强连通分量缩点，这样就可以很容易找出起点和终点之间的所有的桥了。只有删除的边是桥才可能会影响起点和终点的连通性。接下来讨论的就都是起点和终点依旧保持连通的情况。

用Dijkstra算法求出任意一条最短路$L$，将最短路上的边打上标记，并进行连续编号。

容易发现，删除只可能会让最短路增大。如果被删除的边不在最短路上，那么最短路不变，否则需要额外的讨论。

考虑一条边$(u,v)$，经过这条边的所有路可以分成三个连续部分，第一部分和最后一部分的边都打上了标记，而中间部分则都是不打标记的边，且第一部分和最后一部分正好是$L$的前缀和后缀（允许任意部分为空）。

因此对每条边$(u,v)$，我们记录所有经过它的最短路中第一部分最短长度为$L(u,v)$，而记录所有经过它的最短路中最后一部分最短长度为$R(u,v)$。那么很显然删除其余的边后都可以用这条最短路来填补。

我们可以枚举所有边，之后进行区间更新，这个过程可以用线段树来加速，时间复杂度为$O(n\log_2n)$。

最后总的时间复杂度为$O((n+m)\log_2n+q)$。

题目4：给定$n$个顶点$m$条无向带权边构成的连通图，指定起点和终点。之后$q$个请求，第$i$请求询问，假如修改编号为$e_i$的边的权重为$w_i$，要求回答起点到终点的最短距离（注意每个请求不会对之后的请求产生影响）。其中$1\leq n,m,q\leq 10^6$，且每条边的权重为$1$到$10^9$之间

设被修改的边为$e$，那么可以分两类情况讨论，新的最短路是否包含$e$。如果是，非常简单，枚举$e$的两个端点到起点和终点的距离即可。如果不是，那么我们删除$e$也无妨，这就变成题目3所讨论的内容。

总的时间复杂度为$O((n+m)\log_2n+q)$。

提供一道题目。

题目5：给定一个$n\cdot m$的矩阵。初始的时候矩阵中每个单元包含一个数$1$，一个单元格与上下左右四个单元格相连（如果某个边界不存在单元格，则可以从这个边界离开矩阵）。要求回答$q$请求，请求分两类。

1. 将某个单元格中的数从$1$改成$0$。
2. 查询从某个单元格出发离开矩阵，希望经过的所有顶点上数值的总和最小，问最小的总和是多少。

这里$1\leq n,m\leq 500$，$q\leq 10^6$。

我们可以始终维护边界到某个顶点的最短路径的长度（我们将数值和看成长度）。初始时候的最短长度非常好算，因为只可能沿着四个方向走到底。

由于我们一直为每个单元格维护最新的最短路信息，因此请求2都是能$O(1)$回答的。

下面考虑请求1，将某个单元格中的数改成$0$。我们发现首先到这个单元格的最短路一定减少了$1$，并且边上的一些顶点的最短距离可能也发生了改变。这里我们可以用spfa的松弛技术，将这个单元加入到队列中。之后不断向四周进行松弛。

上面的操作看起来比较暴力，但是实际上非常快。由于每个顶点入队，最短距离一定会减少，而每个顶点的初始最短路径均不超过$O(\min(n, m))$，因此这个顶点入队的次数最多也只是如此。总的松弛的时间复杂度为$O(nm\min(n,m))$。

总的时间复杂度为$O(nm\min(n,m)+q)$。

这道题和题目$1$有些类似，都借助了最短路的一些特殊约束。

提供一道题目。

题目6：给定一副包含$n$个顶点$m$条边的有向图，每条边都有边权。且从顶点$1$到其余顶点都至少存在一条路径。且保证初始时顶点$1$到每个顶点的最短距离不超过$1000$。接下来有$q$个请求，请求分为两类：

1. 加入一条新的边$(u,v)$，权重为$w(u,v)$。
2. 查询从顶点$1$到某个顶点$u$的最短距离。

其中$1\leq n,m\leq 10^5, 1\leq q\leq 10^5$。

这个问题和题目5实际上是一样的解法。我们维护最新的最短路信息。这样每当加入一条边的时候，边的两端最多只有一个顶点被松弛。而每个顶点被松弛时都会导致最短距离减少，因此每个顶点被松弛最多发生$1000$次，维护实时最短路信息的总的时间复杂度为$O(1000(n+m+q))$。由于我们维护了实时信息，因此请求2可以直接$O(1)$回答。总的时间复杂度为$O(1000(n+m+q))$。

题目7：给定一副无向图，每条边都有权重，且图连通。其中有一条特殊的边，其权重$x$未知。之后有$m$个约束，每个约束给定两个顶点$u,v$以及它们的最小距离$D_{u,v}$。现在要求找到一个可能的方案，满足所有的约束条件或者报告无解。其中$2\leq n\leq 400,1\leq m\leq 10^6$

容易发现问题可以二分，这样时间复杂度为$(n^3+m)\log_2M$，但是实际上我们可以先把特殊边删除后跑一次Floyd算法，之后可以发现每个约束条件实际上对应于对特殊边权重下界的约束，记这些约束为$a_1,\ldots,a_m$，我们可以直接取$x=\max(a_1,\ldots,a_m)$，容易发现此时所有顶点对距离最小且对于每个约束条件$u,v$，其目前的最短距离一定不小于$D_{u,v}$。之后再跑一次Floyd算法验证即可。

循环依赖等式计算

如果简单的看最短路算法，非常平平无奇，但是考虑最短路实际解决了这样的问题：$dist(u)=\min_{(v,u)\in E}dist(v)+w(v,u)$，其中特殊的有$dist(s)=0$。这里的计算是存在依赖关系的。而考虑到动态规划只能在无环图上计算，因此最短路算法实际上要比动态规划更加强大一些。

接下来我们从解决循环等式的角度来看我们熟悉的最短路算法。要解决循环等式，一个简单的观察就是$dist(u)$是不断递减的，即其不断朝着最终结果接近。我们可以指定多次迭代，即可保证在未来的某一刻，$dist(u)$就是最优解。这个过程实际上就是Bellman-Ford算法。但是我们可以更加优化这个过程，比如上一次迭代的时候仅更新了$dist(v)$，那么下一次迭代仅需要考虑那些存在边$(v,u)$的顶点$u$。而这个算法实际上就是我们非常常用的SPFA算法。

如果还能发现$w(v,u)\geq 0$，那么可以只有距离较小的的顶点，可以优化距离较大的顶点。这里给了我们一种类似拓扑关系的能力，我们可以保证当$dist(u)$是最小未确定的变量的时候，那么$dist(u)$就是它的最终解，有了这一层观察，我们可以维护一个数据结构，来实时查询函数值最小的未确定变量，这就是我们常用堆来优化dijkstra算法。

了解了这些内容后，我们可以发现实际上对于不等式，我们将所有变量定义为顶点，而它们的依赖关系定义为有向边，之后我们在图上求解。如果它通过不断迭代可以不断接近最终结果，那么我们就可以用Bellman-Ford或者SPFA算法来暴力求解，并且这时候只要没有负环，迭代次数会约束到$O(V)$。如果还能保证只有函数值较小的顶点能优化函数值较大的顶点，那么可以用更加高效的Dijkstra算法来解决。

题目1：给定$n$个顶点$m$条边的有向图$G=(V,E)$。我们在顶点$1$放一个机器人，机器人会随机选择一条出边移动，如果没有出边，则机器人停留在原地。现在要求选择一组顶点，删除它们任意多的出边，要求机器人最终一定会停止在顶点$n$，或者报告它是不可能的。要求选择的顶点数最少，求这个最少顶点数。

提供一道题目。

定义$f(u)=\min(1+\min_{(u,v)\in E} f(v),\max_{(u,v)\in E}f(v))$。其中$f(u)$表示从$u$出发，最少需要选择多少个顶点，能保证机器人最后一定会停止在顶点$n$。

那么我们现在面对了一个循环依赖等式，可以发现可以迭代使得所有变量更加接近最终值，因此可以用Bellman-Ford算法求解。但是实际上这里可以发现$f(u)$一定是被更小的$f(v)$优化的，因此可以用Dijkstra算法来求解。

最终的时间复杂度为$O(E\log_2E)$。