我试着用谷歌搜索，但没有任何有价值的东西弹出。
图表：
是无向的。
表示为具有双边的有向图。
可能包含负权重的边。
我知道我可以使用bellman-ford来解决定向情况下的问题，但对于无向边，它只会返回单边（2个循环）作为输出。我需要找到一个大于2的循环。
此外，该算法应该具有运行时复杂度O（V*E）和存储器复杂性O（V）。
最佳答案
查看Bellman-Ford algorithm，在步骤2中，您考虑使用每个边（u，v）来找到到v的较短路径，如果您看到改进，则通过设置precondence[v]=u来记录它。这意味着在每个阶段您都知道每个节点的precondence，因此您可以通过检查precondence[u]来消除长度两个周期！=v，然后设置前置任务[v]=u。
通过消除这些循环，你可以改变归纳法的不变量-在每个阶段，你现在可以找到从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
...
这里有一个证据表明，在存在负周期的情况下，距离将继续无限期地变化：
如果不是这样然后有一个稳定的距离分配：任何可能的距离更新都不会减少它这意味着，检查边的顺序（可能会减少距离）是不相关的，因为在这种情况下，每个边在检查时都保持距离不变。
在一个负循环中选择一个点，并考虑从该点一直走到它环绕并再次到达自身的路径由于检查此路径中的第一条边会使所有内容保持不变，因此该边远端的距离减去该边近端的距离不得大于沿该边的距离。类似地，沿路径两步的距离减去路径开始处的距离，不得大于沿相关两条边的距离之和，否则我们会将距离更新到两点的更远处。接着，我们计算出（圆形）路径末端的距离必须不超过（圆形）路径的起点加上沿该路径的边的总和，否则将更新某些内容。但是路径的起点和终点是同一点，因为它是圆的，并且沿边的距离之和是负的，因为它是负的循环，所以我们达到了一个矛盾，事实上，一旦我们检查了沿圆路径的所有边，就必须有一些更新。