java - 检查权重总和不为 0 的循环

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 到它自身的所有路径/循环，并检查它们是否全部加起来为 0。我在以有效方式查找所有路径/循环时遇到问题，是否有更优雅的解决方案，或者我应该尝试找到最有效的算法来查找所有路径？

Answer 1

如果我没理解错的话，这个问题等同于“对于给定的顶点 v，对于任何其他顶点，检查从 v 到该顶点的所有路径是否具有相同的权重”。

我想你可以通过 BFS 做到这一点，只需用与 v 的距离标记顶点，并检查遍历时是否有不同的距离。

换句话说，由于从起始顶点到某个顶点的所有距离都应该相同，因此您可以为每个顶点创建具有该距离的标签。从给定的起始顶点开始，BFS 遍历所有顶点的。遍历图时，对于每个顶点 v，检查尾部为 v 的所有边。计算v的label加上边的权重，得到一个值x(v肯定已经被label了)。对于边的头顶点w，有两种可能:

1. w 没有标签。然后用值 x 标记 w。

2. w 已被标记。在这种情况下，比较x 和w 的标签。

   • 如果相同，继续检查。
   • 否则，您将得到一个边数最少的圆，因为您正在进行 BFS。立即停止。

当从v 开始的所有边都被选中时，转到BFS 中的下一个顶点。如果所有顶点都通过了测试，则不存在这样的圆。

希望这对您有所帮助!