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

Question

我有一个连通图 g，它有 n 个顶点和 m 个边。

每条边都可以从两个方向遍历，从一个方向遍历权重为正，从另一个方向遍历权重为负。

因此对于权重为 w 的每条边 u -> v 都存在一条边 v -> u，权重为-w。

我的目标:

对于给定的顶点v，检查是否存在返回v的路径(循环)使得该路径的边权重之和不相等到 0。如果存在这样的路径，则输出该路径的最小边数，否则输出"all cycles are fine"。

示例:

一个示例，其中从 v 到 v 的所有路径总和为 0。输出是“所有周期都很好”:

一个示例，其中存在从 v 到 v 的路径，其边缘总和不等于 0。在此示例中，此类路径的最小边数为 4:

我目前的做法:

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

Answer 1

检查是否存在通过顶点 A 的“错误循环”的简单算法是从 A 运行 BFS，然后查看以不同成本至少访问了哪些顶点 B 两次。如果不存在 B，则所有循环都是好的，否则存在大小为(直到第一次访问 B 的边)+(直到以不同成本访问 B 的边)的坏循环。这个 BFS 最多访问每个顶点两次，所以复杂度仍然是线性的。

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