检查权重不为0的环路

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

- PlsWork

Answer 1

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

我猜你可以通过BFS来解决这个问题，只需标记距离v的顶点，并在遍历时检查是否存在不同的距离。

换句话说，由于从起始顶点到某个顶点的所有距离应该相同，因此您只需为每个顶点创建具有该距离的标签。从给定的起始顶点开始，BFS遍历所有顶点。对于每个顶点v，当您遍历图形时，请检查其尾部为v的所有边缘。计算标签v加上边缘的权重并获得值x（v必须已被标记）。对于边缘的头顶点w，有两种可能性：

1. w未被标记。然后用值x标记w。 2. w已经被标记。在这种情况下，请比较x和w的标签。

如果它们相同，请继续检查。否则，由于您正在进行BFS，因此您将具有最小数量的边缘圆圈。立即停止。

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

希望这可以帮助您！

- aleph0

---

有趣的想法，从顶点v到顶点w的所有路径应该具有相同的长度，因为如果存在两条不同长度的从v到w的路径，我们可以使用其中一条路径到达w，另一条路径返回v，由于我们假设这两条路径的长度不同，所以边权重之和必须不等于0。现在来看第二部分，目标是检查从v到每个顶点w的所有路径是否具有相同的长度，您能否详细说明如何通过使用BFS来实现这一目标？ - PlsWork

好的，我明白了如何使用BFS检查不加起来为0的循环，但我不明白如何确保该循环具有最小数量的边缘？我如何确定该最小循环的长度（边权重之和）？ - PlsWork

通过使用BFS，您可以了解从起始顶点到当前顶点的边数。在这种情况下，您可以创建另一个标签n：从起始顶点到当前顶点的最小边数。当您遇到具有不同距离的顶点w时，如上所述，您将拥有一个圆，其边数是两部分之和：w的n和从起始点到v的边数。第二部分必须是最小的，因为我们正在进行BFS。对于第一部分，请尝试所有可能的w并选择最小的一个。 - aleph0

你所描述的算法适用于几乎所有情况，但有些情况下顶点遍历的顺序很重要（在找到“坏环”后立即停止会得出错误的答案）。我的最终解决方案是进行完全BFS，存储所有“坏环”的大小并输出最小值。 - PlsWork