检查从顶点v到另一个顶点w的所有路径是否具有相同的长度

Question

我有一个连接图g和n顶点和m边。

每条边都可以从两个方向穿过，而在一个方向上穿过它们的重量是正的，在另一个方向穿过它们并且它们的重量是负的。

因此，对于每一个边缘u - >v体重w存在一个边缘v - >u体重-w。

我的目标：

对于给定的顶点v，检查是否存在一个路径回v（一个周期），因此该路径的边缘权重的总和不等于0。如果存在这样的路径，则输出该路径的最小数量的边缘，否则输出"all cycles are fine"。

实例：

一个例子，其中从v到v总和的所有路径可达0。输出为"all cycles are fine"：

在存在路径从v到v其边缘总结到的东西是不等于0一个例子。这样的路径的边的最小数目是4在该实例中：

我目前的做法：

这个问题似乎是等效于检查是否从一给定顶点v所有路径到任何其他顶点w的长度相等，如果这是真的，那么“所有周期都很好”，否则我输出打破条件的最短周期的长度。我无法找到一个有效的算法来测试这种情况。

Answer 1

检查是否存在通过顶点A的“错误周期”的简单算法是从A运行BFS，然后查看哪些顶点B至少以不同成本访问过两次。如果没有B存在，那么所有的周期都是好的，否则就会有一个不好的周期（边缘直到第一次访问B）+（边缘直到以不同的成本访问B）。这个BFS最多访问每个顶点两次，所以复杂度仍然是线性的。

因此，这个问题可以用图中每个顶点的BFS来解决。当然，也许这可以提高效率;什么是足够的取决于n和m的大小。