听说读论文的最好方法是把它翻译一遍。。?(然而我不会严格地翻译。。只会大概地复述一遍。。)这次的论文是《All Pairs Shortest Paths in weighted directed graphs - exact and almost exact algorithms》(Zwick'98)。论文的主题是有向带权图的APSP(All Pair Shortest Path，两两最短路)问题。

本文所有信息来自论文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镇站之宝我拿这东西出题干嘛

看到绿色夹克衫大爷[5]研究过这个东西。。就来玩了一发。。觉得这个居然可以在多项式时间做出来。。优美啊

复杂度应该是$O(n^3)$乘高精度。。模意义的话不一定资瓷，因为要开方

这篇文章基本上是[1]的一个翻译。。不能算翻译吧因为不是严格一句一句翻的，但是大概就是把[1]用中文说了一遍owo

有一些证明[1]中没有给出，其中Muir的定理证明和Kasteleyn定理的引理1证明是我自己证的，其他的都是搬运。可能各种地方不够严谨、表述不清什么的。。请不吝提出，欢迎打脸。。

以及。。这些算法我都完全没有实现过。。真·嘴巴选手