我有一个连通图g，具有n顶点和m边。
每个边都可以从两个方向遍历，当在一个方向遍历它们时，它们的权重是正的，在另一个方向遍历它们，它们的权重是负的。
所以对于每个边u-
我的目标：
对于给定的顶点v，检查是否存在返回v的路径（一个循环），以便该路径的边权重之和不等于0。如果存在这样的路径，则输出这样的路径的最小边数，否则输出“所有循环都很好”。
例子：
从v到v的所有路径总和为0的示例。输出是“所有循环都很好”：
存在从v到v的路径的示例，其边缘总和不等于0。在此示例中，此类路径的最小边数为4：
我目前的做法：
这个问题似乎相当于检查从给定顶点v到任何其他顶点w的所有路径是否长度相等，如果这是真的，那么“所有循环都很好”，否则我输出打破条件的最短循环的长度。我很难找到一个有效的算法来测试这个条件。
检查是否存在经过顶点A的“错误循环”的一个简单算法是从A运行一个BFS，然后查看哪些顶点B以不同的代价被访问了至少两次。如果没有B存在，那么所有循环都是好的，否则存在一个大小（直到第一次访问B的边）（直到以不同的代价访问B的边）的坏循环。这BFS访问每个顶点最多两次，因此复杂度仍然是线性的。
因此，这个问题可以用图中每个顶点的BFS来解决。当然，也许这可以变得更有效；什么是适当的取决于n和m的大小。
