无权图增量最短路问题

本文所有信息来自论文Incremental Algorithms for Minimal Length Paths。

今天我们要介绍一个数据结构，它解决如下的问题：有一张有向无权图，要求在线地支持三种操作：

• 加入一条边
• 求两点之间最短路长度
• 求两点之间的最短路(整条路径)

这个数据结构的复杂度如下：加入所有$O(n^2)$条边，总复杂度是$O(n^3\log n)$；求最短路长度是$O(1)$的，而且是查表(就是说，没有任何加减乘除运算)；求最短路是$O(L)$的，其中$L$是最短路长度。空间复杂度是$O(n^2)$的。

这是个很优秀的复杂度。。因为Floyd也就$O(n^3)$。对于这种动态问题，如果询问就是查表的话总的更新复杂度至少是$O(n^3)$(论文里有讲)。论文一开头就说他们离best possible bound只差了一个$\log n$。

然后，我猜这个算法对带权图也是对的，但是复杂度(具体地说，对后面的$\sum |B_{ij}|$的分析)就不对了。

至于会不会出成OI题?我又不是cc镇站之宝我拿这东西出题干嘛

数据结构

为了搞清楚这个算法的执行过程，我们首先需要了解这个算法维护的数据结构。

首先作为一个查表的算法，我们肯定要维护一个表$D_{ij}$表示$i$和$j$之间的最短距离。

对每个节点$v$，我们维护两棵树$DESC(v)$和$ANC(v)$。$DESC(v)$为以$v$为起点的最短路树(bfs树)，$ANC(v)$为把所有边方向取反之后以$v$为起点的最短路树。

然后，我们维护两个表格$FORWARD[u,v]$和$BACKWARD[u,v]$。$FORWARD[u,v]$指的是在$DESC(u)$中$v$的位置(即，一个指向$DESC(u)$中节点$v$的指针)；如果$u$无法到达$v$那么$FORWARD[u,v]=\text{NULL}$；$BACKWARD[u,v]$指的是在$ANC(u)$中$v$的位置(细节同$FORWARD[u,v]$)。

算法流程

询问最短路距离很简单，查表就好。

询问$u$到$v$的最短路径，只需要在$DESC(u)$中沿着$FORWARD[u,v]$一路往父亲跳，跳到$u$就是最短路。

上面两个都很简单，真正难的是加入一条边之后如何更新这个数据结构。考虑插入一条边$i\to j$，我们可以想象是用$DESC(j)$来更新$ANC(i)$中的所有点。同时，只有$DESC(j)$中的点的$ANC$和$ANC(i)$中的点的$DESC$会被更新。

怎么更新?考虑$u\in ANC(i)$，$v\in DESC(j)$，则$D[u,v]$被更新为$\min(D[u,v],D[u,i]+1+D[j,v])$。考虑以下两种情况：

1. $D[u,v]>D[u,i]+1+D[j,v]$。那么更新后$v$在$DESC(u)$中，且其父亲就是$v$在$DESC(j)$中的父亲($v=j$时$v$父亲是$i$)。如果$v$本来就在$DESC(u)$中，我们需要将$v$删掉，重新插入到其父亲底下。
2. $D[u,v]\le D[u,i]+1+D[j,v]$。此时我们有结论：$DESC(j)$的$v$所在子树无法对$INC(i)$的$u$所在子树做任何的贡献了。因为设$v_0$是$DESC(j)$的$v$所在子树中的点，$u_0$是$INC(i)$的$u$所在子树中的点，那么更新前$D[u_0,v_0]\le D[u_0,u]+D[u,v]+D[v,v_0]\le D[u_0,u]+D[u,i]+1+D[j,v]+D[v,v_0]=D[u_0,i]+1+D[j,v_0]$。

我们发现第2条相当于一个剪枝。我们给出完整的算法(伪代码可以去论文上看)：考虑一棵树$T$，用UpdateForward($x,i,j,T$)表示：用$T$来更新$ANC(i)$中的子树$x$内所有点的$DESC$。一开始我们要用$DESC(j)$来更新$ANC(i)$内所有点的$DESC$，那么调用UpdateForward($i,i,j,DESC(j)$)。下面考虑UpdateForward的过程。我们首先对$T$中每个点$y$，用$D[x,i]+1+D[j,y]$更新$D[x,y]$，如果更新不成功那么将$y$所在子树剪掉，否则(更新成功)也连带着更新$DESC(x)$这棵树的结构。接下来对$x$的所有儿子$x_0$我们调用UpdateForward($x_0,i,j,T'$)，其中$T'$是剪过的$T$。

这样就完成了对所有$DESC$的维护。对$ANC$的维护是类似地。在往一棵树内插入节点的时候，我们顺便维护一下$FORWARD$和$BACKWARD$两个数组。

回溯的时候重新将$T'$变成$T$，上述的一切基本操作是可以$O(1)$完成的(没必要用LCT，因为你只需要换父亲和维护父亲、儿子)。

复杂度证明

我们考虑插入边$(i,j)$时，会有两种事情发生：

• 考虑了$ANC(i)$中的点$x$和$DESC(j)$中的子树$y$，且$D[x,y]$被这条边更新了；我们称这样的点对$(x,y)$是benign for $(i,j)$的，这样的$(x,y)$集合为$B_{ij}$；
• 考虑了$ANC(i)$中的点$x$和$DESC(j)$中的子树$y$，且$D[x,y]$没有被这条边更新(当然接下来会迎来一波剪枝)；我们称这样的点对$(x,y)$是malign for $(i,j)$的，这样的$(x,y)$集合为$M_{ij}$。

复杂度就是$\sum_{(i,j)}|B_{ij}|+|M_{ij}|$。

我们先来分析$\sum |B_{ij}|$。我们假设一开始$D$中的值都是$n+1$(代表$+\infty$)，每一对$(x,y)\in B_{ij}$一定更新了矩阵$D$，至少减少了$1$。$D$的权值和从$O(n^3)$变成了一个非负整数，所以$\sum |B_{ij}|=O(n^3)$。

$\sum |M_{ij}|$不是很好分析，论文中给出的是势能分析法：在插入$(i,j)$的时候，对所有benign pair $(x,y)$，给点$x$和点$y$各增加$2\frac{n}{d(x,y)-1}$的势能；给$i,j$各增加$2n$的势能。对于一对点$(x,y)$而言，每给一次势能$d$就会减少至少$1$，从而势能总量是$O(\sum_{d=1}^n\frac{n}{d})=O(n\log n)$的，那么总势能是$O(n^3\log n)$的。接下来要证明这些势能是够用的。事实上，插入$(i,j)$时的势能总量大于等于$|M_{ij}|$。

若$(x,y)\in M_{ij}$，记$\pi_x$为$ANC(i)$中$x\to i$的路径上的所有点(不包括$x$)，$\pi_y$为$DESC(j)$中$j\to y$的路径上所有点(不包括$y$)，$d_x,d_y$分别为$|\pi_x|-1,|\pi_y|-1$，则由$\pi_y$引起的$x$的势能总量为$\sum_{h=d_x}^{d_y+d_x-1}\frac{2n}{h}\ge 2n\ln(1+\frac{d_y}{d_x})$；由$\pi_x$引起的$y$的势能总量为$\sum_{h=d_y}^{d_y+d_x-1}\frac{n}{h}\ge 2n\ln(1+\frac{d_x}{d_y})$。这样，$x$和$y$这两个点上至少有$2n\ln((1+\frac{d_y}{d_x})(1+\frac{d_x}{d_y}))=2n\ln(2+\frac{d_x}{d_y}+\frac{d_y}{d_x})\ge 2n\ln 4\ge 2n$的势能，这些势能足以支付$(x,*)$和$(*,y)$类型的所有malign pairs。

我们每次从$M_{ij}$中找出一个元素$(x,y)$，用完$x$和$y$上的所有势能，并从$M_{ij}$中删除所有形如$(x,*)$，$(*,y)$的malign pairs。我们删除的malign pairs的个数不会有$x$和$y$上的所有势能加起来那么多。然后继续找元素$(x',y')$，则$x',y'$的势能肯定都没有被用过，那么这个过程就可以继续，直到$M_{ij}$被删光了为止。从这里可以看出，插入$(i,j)$时的势能至少有$|M_{ij}|$这么大。

这样，$\sum |M_{ij}|=O(n^3\log n)$，总的复杂度也就是$O(n^3\log n)$了。