无权图增量最短路问题

r_64 posted @ 2016年12月07日 14:59 in 未分类 with tags 黑科技 , 939 阅读

本文所有信息来自论文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)$了。

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter