algorithm - 在无向图中寻找负循环

Question

我尝试用谷歌搜索它，但没有弹出任何有值(value)的信息。

图表:

• 是无向的。
• 表示为具有双边的有向图。
• 可能包含负权重的边。

我知道我可以在有向情况下使用 Bellman-Ford 来解决这个问题，但是对于无向边，它只会返回单边(2 周期)作为其输出。我需要找到一个大小 > 2 的循环。

此外，该算法应该具有运行时复杂度 O(V*E) 和内存复杂度 O(V)。

Answer 1

查看 Bellman-Ford algorithm ，在第 2 步中，您考虑使用每条边 (u, v) 来找到到 v 的更短路径，如果您看到改进，则通过设置前驱 [v] = u 来记录它。这意味着在每个阶段您都知道每个节点的前驱 - 因此您可以通过在设置前驱 [v] = u 之前检查前驱 [u] != v 来消除两个循环的长度。

通过消除这些循环，您改变了归纳法的不变量 - 在每个阶段，您现在找到从 s 到 u 的最短路线，最多 i 条边不包括任何长度的 2 个循环。

从源可到达的长度为 3 或更大的循环应该仍然显示 - 在您应该找到长度达到访问每个顶点所需的长度的每条最短路径之后，对负循环的检查会寻找明显的改进。

示例:考虑 G = {{A, B, C, D}, {AB=2, AC=2, BC=-3, BD=1, CD=1}}。

更新，更新 B，然后更新 C，然后更新 D:

A=0，B=C=D=无穷

A=0，B=2 来自 A，C=-1 来自 B，D=0 来自 C

A=0，B=1 来自 D，C=-2 来自 B，D=-1 来自 C

A=0，B=0 来自 D，C=-3 来自 B，D=-2 来自 C

A=-1 来自 C，B=-1 来自 D，C=-4 来自 B，D=-3 来自 C...

这里有一个证明，即在存在负循环的情况下，距离将无限期地继续变化:

否则假设。然后有一个稳定的距离分配:任何距离的更新都不会减少它。这意味着检查可能减少距离的边的顺序是无关紧要的，因为在这种情况下，每条边在检查时都会保持距离不变。

在负循环上选择一个点，并考虑从该点开始的路径，直到它环绕并再次到达自身。由于检查此路径中的第一条边后一切都没有改变，因此该边远端的距离减去该边近端的距离必须不超过沿边的距离。类似地，沿路径两步的距离减去路径起点的距离必须不超过沿相关两条边的距离之和，否则我们会将距离更新为两点中较远的一点。继续，我们计算出(圆形)路径末端的距离必须不超过(圆形路径)的起点加上沿该路径的边的总和，否则某些东西会被更新。但是路径的起点和终点是同一个点，因为它是圆的，沿边的距离之和是负的，因为是负循环，所以我们就矛盾了，其实肯定有更新一旦我们检查了沿圆形路径的所有边缘。