注册 留言板
当前位置:首页 > 方法论 > 数据结构 > 正文

The Minimum Cycle Mean in a Digraph 《有向图中的最小平均权值回路》 Karp

来源:CNBLOGS   发布时间: 2017-06-19   作者:网友   浏览次数:
摘要: 文件链接 Karp在1977年的论文,讲述了一种\(O(nm)\)的算法,用来求有向强连通图中最小平均权值回路(具体问题请参照这里) 本...

文件链接

Karp在1977年的论文,讲述了一种\(O(nm)\)的算法,用来求有向强连通图中最小平均权值回路(具体问题请参照这里

本人部分翻译:

首先新建一个节点 \(s\) ,从它到每个点连一条权值任意(比如都为0)的边,然后,定义 \(F_k(v)\) 为从 \(s\)\(v\) 恰好经过 \(k\) 条边的最短路(不存在则为 \(\infty\) ), \(\lambda^*\) 表示答案,则

Theorem 1

\[\tag{1}\label{theorem}\lambda^* = \min_{v \in V} \max_{0 \leq k \leq n - 1} \left[\frac{F_n(v)-F_k(v)}{n-k}\right]\]

定理1的证明需要一个引理。

Lemma 2

如果\(\lambda^* = 0\),那么

\[\min_{v \in V} \max_{0 \leq k \leq n - 1} \left[\frac{F_n(v)-F_k(v)}{n-k}\right] = 0\]

Proof. 由于 \(\lambda^* = 0\) , 存在一个零环,但不存在负环。由于没有负环,从 \(s\)\(v\) 一定存在最短路,且其长度不超过 \(n\) 。令其为 \(\pi(v)\) , 则 \(F_n(v) \geq \pi(v)\) , 且 \(\pi(v) = \min_{0 \leq k \leq n - 1} F_k(v)\) , 那么

\[F_n(v) - \pi(v) = \max_{0 \leq k \leq n - 1} [F_n(v) - F_k(v)] \geq 0\]

且有

\[\tag{2}\label{lemma}\max_{0 \leq k \leq n - 1} \left[\frac{F_n(v)-F_k(v)}{n-k}\right] \geq 0\]

\((\ref{lemma})\) 中等号成立当且仅当 \(F_n(v) = \pi(v)\) . 现在我们只需要证明存在这样一个节点就可以完成此引理的证明。由条件可知,图中存在零环。令此零环为 \(C\) ,在环上任选一点 \(x\) , 沿环上的边走若干步后到 \(x\) , 那么 \(s\rightarrow x\rightarrow y\) 一定是一条 \(s-y\) 最短路(不然就可以构造出一个负环)。那么,从 \(x\) 出发沿零环走若干步直到 \(s\rightarrow x\rightarrow y\) 长为\(n\) 时,就有 \(F_n(y) = \pi(y)\) , 即\[\max_{0 \leq k \leq n - 1} \left[\frac{F_n(v)-F_k(v)}{n-k}\right] = 0\]. 证毕。

Proof of Theorem 1. 我们现在讨论将图中所有边权都减少 \(c\) 之后定理1中的两边会怎么变化。 \(\lambda^*\) 会减少 \(c\) , 因为所有环的平均权值都减少了 \(c\) . \(F_k(v)\) 会减少 \(kc\) ,

\[\min_{v \in V} \max_{0 \leq k \leq n - 1} \left[\frac{F_n(v)-F_k(v)}{n-k}\right]\]

也会减少 \(c\) . 所以定理1等号两边都减少了相同的量。我们选择一个 \(c\) 使得此过程后 \(\lambda^*=0\) , 再应用定理2,则定理1成立。 证毕。

我们可以通过下述递推式求出所有 \(F_k(v)\) :

\[F_k(v) = \min_{(u, v) \in E} \left[F_{k - 1}(u) + w(u, v)\right],\,k=1,2,...,n\]

其初始条件

\[F_0(s)=0; F_0(v)=\infty,v\neq s\]

由于每条边会被松弛 \(O(n)\) 次,最后求出 \(\lambda^*\) 的值需要 \(O(n^2)\) , 总时间复杂度为 \(O(nm)\) .

刘汝佳老师在《算法竞赛入门经典——训练指南》(即通常说的蓝书)上提到过此算法(P334), 他写道“应用到本题时需要先找出强连通分量”, 实际上不必如此(以下原创)。

计算 \(\lambda^*\) 时,由于我们从 \(s\) 向每个点连了一条边,对于每个 \(v\) , 满足 \(F_k(v) \neq \infty\)\(k\) 的区间一定是从 \(1\) 开始的连续的区间。那么,若 \(F_n(v) = \infty\) , 其一定不在任何一个环上,可以忽略。而证明中其它地方都没有利用强连通的性质,所以定理1依然成立。

所以,对于任意有向图\(G\), 若我们认为\(\infty - \infty = \infty\)

\[\lambda^*=\min_{v \in V} \max_{0 \leq k \leq n - 1} \left[\frac{F_n(v)-F_k(v)}{n-k}\right]\]



我来说两句
评论内容:
验  证  码:
 
(网友评论仅供其表达个人看法,并不表明本站同意其观点或证实其描述。)
评论列表
已有 0 条评论(查看更多评论)
精彩专题
  • 本月排行
  • 总排行
友情链接:
QQ交流群:①群 155252576 INFOCOOL官方交流群 ②群 469193068 WEB前端技术交流群 ③群 531831996 数据库交流群 ④群 243504572 编程技术交流群
设为首页 - 加入收藏 Copyright @2016 Infocool 版权所有 粤ICP备16000626号