我尝试用谷歌搜索，但没有弹出任何有值(value)的内容。
图表:
- 无向。
- 表示为具有双边的有向图。
- 可能包含负权重的边。
我知道我可以使用 Bellman-Ford 在有向情况下解决这个问题，但对于无向边，它只会返回单边(2 个周期)作为其输出。我需要找到一个大小 > 2 的循环。
此外，该算法应该具有运行时复杂度 O(V*E) 和内存复杂度 O(V)。
最佳答案
查看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) ...
这里有一个证明，证明在存在负循环的情况下距离将无限期地继续变化:
否则的话。然后有一个稳定的距离分配:任何距离的更新都不会减少它。这意味着检查可能减少距离的边的顺序是无关紧要的，因为在这种情况下，每条边在检查时都会使距离保持不变。
在负循环上选择一个点，并考虑从该点开始直到它绕一圈并再次到达自身的路径。由于检查该路径中的第一条边会使所有内容保持不变，因此该边远端的距离减去该边近端的距离必须不大于沿该边的距离。同样，沿路径两步的距离减去路径起点的距离必须不大于沿相关两条边的距离之和，否则我们会将距离更新为两点中较远的点。继续下去，我们发现(圆形)路径末端的距离必须不超过(圆形路径)的起点加上沿该路径的边的总和，否则某些内容将被更新。但是路径的起点和终点是同一个点，因为它是圆形的，并且沿边缘的距离之和为负，因为它是负循环，所以我们遇到了矛盾，实际上必须进行一些更新一旦我们检查了圆形路径上的所有边缘。
关于algorithm - 寻找无向图中的负循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22487004/