删边最短路问题

dengyaotriangle · 2020-11-30 15:51:01 · 个人记录

问题

给定正权无向图 G，求其删掉每一条边之后的 1 到 n 最短路长度（保证存在）。

做法

注意，以下的做法如果改成有向图，就是错的！ 文末将给出一个反例，以及在哪一步证明证不下去了。

大多数的做法是这样的，任取某一条 1 到 n 的最短路，记为 1\rightsquigarrow n（令 i\rightsquigarrow j 代表 i 到 j 的最短路，下同）。若边 (i,j) 不在 1\rightsquigarrow n 上，则显然最短路不会改变。所以只考虑 1\rightsquigarrow n 上的边删去的效果。

我们考虑所有边 (i,j)，我们求出强制经过这条边 (i,j) 的 1 到 n 的最短路，显然为了最短，是 1\rightsquigarrow i \to j \rightsquigarrow n。

之后，我们考虑某一条 1\rightsquigarrow i \to j \rightsquigarrow n 与 1\rightsquigarrow n 的交集 I，用 \operatorname{len}(1\rightsquigarrow i \to j \rightsquigarrow n) 更新所有 1\rightsquigarrow n 上不属于 I 的边的答案（更新就是取 \min）

这个看上去有一定的道理，我们相当于依次强制最短路走过每条其他的边，然后看这样形成的最短路径避开了 1\rightsquigarrow n 上的哪些边，更新这些边的答案。

但是这个做法有一个问题，我们怎么知道，强制 一条边 就够了呢，为什么不需要强制两条或者更多？注意到大部分题解并没有证明它的正确性，接下来我们证明它是对的。

证明

我们令 G 从 1 出发的最短路树为 S（有多个则任取），考虑 1\rightsquigarrow n 上任意一条边 (i,j)，显然 i\to j 在 S 中。

考虑 j 为根的子树 S_1 ，令 S 除去 S_1 的部分为 S_0，我们首先知道 S_0 中的点 u，1\rightsquigarrow u 不会变。这是因为考虑 dijkstra 构造最短路树的过程，首先每个点 1\rightsquigarrow x 不会变小，而 S_0 中的点由于不在 j 的子树内，所以不依赖于 i\to j ，所以不会变大。不会变大变小，所以不变。

现在令 G 从 n 出发的最短路树为 T（有多个则任取），同样的，我们可以求得 T_0,T_1 代表最短路树中不在 i 的子树的和在 i 的子树的。

令所有点构成的集合为 V，那么我们显然有 S_0\cup S_1=T_0 \cup T_1=V，且 S_0\cap S_1=T_0\cap T_1=\varnothing。

我们现在有一个非常重要的观察，就是 S_1\cap T_1=\varnothing，或者说，没有任何一个节点 u 在 1 的最短路树上处于 j 的子树内，也在 n 的最短路树上处于 i 的子树内。

这个原因是假设存在这样的节点 u，考察 1\rightsquigarrow u，而 u 在 1 最短路树中处于 j 的子树内，所以 1\rightsquigarrow u=1\rightsquigarrow i \to j \rightsquigarrow u，同理由于它也在 n 的最短路树上属于 i 的子树，u\rightsquigarrow n=u \rightsquigarrow i \to j \rightsquigarrow n。

这似乎还不能导出矛盾，那么我们把它和 1\rightsquigarrow n 合在一起看呢？1\rightsquigarrow n = 1\rightsquigarrow i \to j \rightsquigarrow n。

\begin{matrix}&&&u&&&\\ & &\nearrow& &\nwarrow& & \\1& \rightsquigarrow & i& \to& j& \rightsquigarrow &n\end{matrix}

（那两个斜着的箭头应该是弯的，但由于博客的限制打不出来）

我们令 \operatorname{len}(i\to j)=a，\operatorname{len}(i\rightsquigarrow u)=b，\operatorname{len}(j\rightsquigarrow u)=c

由于 1\rightsquigarrow i \to j \rightsquigarrow u 是最短的，那么一定有 \operatorname{len}(i \to j \rightsquigarrow u)\leq\operatorname{len}(i \rightsquigarrow u)，这得出 a+c\leq b，同时 u \rightsquigarrow i \to j \rightsquigarrow n 最短告诉我们 a+b\leq c。

二式相加，2a\leq 0，由于正权，矛盾。

所以说，S_1\cap T_1=\varnothing，这告诉我们 S_1 \subseteq T_0，这有何用？我们接着看。

考虑任意一条 1\rightsquigarrow n，它一定只经过 S_0 内部的边，两个节点分别属于 S_0,S_1 的边，和都属于 S_1 的边这三种。

首先，这条最短路径上必须至少有一条分别属于 S_0,S_1 的边，因为 1\in S_0,n\in S_1。

取最后一条这样的边，设为 (u,v)，首先，这条最短路上 v\rightsquigarrow n 中所有点均属于 S_1，而 S_1\subseteq T_0，v\rightsquigarrow n 中所有点都属于 T_0，这说明 v\rightsquigarrow n 中没有一条边是 (i,j)，且长度就是 T 中 v 的距离。

接下来考察 u，我们取 S_0 树上的 1\rightsquigarrow u，它显然至少不长于我们取的这条最短路的 1\to \cdots \to u。所以说 1\rightsquigarrow u\to v \rightsquigarrow n 不长于最短路，所以它与最短路等长。

同时，由于 1\rightsquigarrow u 中每个点都属于 S_0，我们也可以导出它也不包含 (i,j) 且长度就是 S 中 u 的距离。所以 1\rightsquigarrow u\to v \rightsquigarrow n 不长于最短路且满足条件。

综上所述，一定存在一条 (u,v) 满足：

1\rightsquigarrow u\to v \rightsquigarrow n$ 不经过 $(i,j)

综上，得证。也就是说，对于任何一个最短路上的 (i,j) 一定存在一条边 (u,v) 满足强制走过 (u,v) 的某一条最短路就是删去 (i,j) 的最短路，那个做法就是对的了。

有向图错在了哪里

graph_editor，请。这个图如果要删掉 (2,4) 这条边，就必须同时强制 (1,3),(3,5) 全部选择才行，任意强制走一条边的最短路都会经过(2,4)

那么证明错在了哪里？我们看那个证明 a+b<c,a+c<b 的部分，我们发现，这个其实是假设了路径可以翻转，但是，有向图破坏了这个假设，所以就证不出来了。

零权边？

也可以做，我们需要稍微修改这个过程，我们首先确定任意一条最短路 1\rightsquigarrow n ，然后在构建 S 的时候，尽可能的将一个节点与 n 的 lca 变高。这样我们发现，如果 2a\leq 0，这导出 a=0，也就是 b=c，此时我们发现，这个新的最短路并没有满足lca最短（有相同长度但lca更高的），所以就可以啦。

所以我们需要将边权为 0 缩联通块，来构建这样的 S,T，就可以了。

或者换句话说，零权边使得结论弱化为了对于任何一个最短路上的 (i,j) 一定存在一条边 (u,v) 满足强制走过 (u,v) 的，与 1\rightsquigarrow n 交集最小 的最短路就是删去 (i,j) 的最短路，那个做法就是对的了。