检查权重总和不为 0 的循环
Check for cycles whose weights don't sum up to 0
我有一个连通图 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 到它自身的所有 paths/cycles 并检查它们是否全部加起来等于 0。我在以有效方式找到所有 paths/cycles 时遇到问题，是否有更优雅的解决方案，或者我应该尝试找到找到所有路径的最有效算法？
如果我没理解错的话，这个问题等同于"For a given vertex v, for any other vertex's, check if all paths from v to that vertex have a same weight"。
我想你可以通过 BFS 做到这一点，只需用与 v 的距离标记顶点，并检查遍历时是否有不同的距离。
换句话说，由于从起始顶点到某个顶点的所有距离都应该相同，因此您可以为每个顶点创建具有该距离的标签。从给定的起始顶点开始，BFS 遍历所有顶点的。遍历图时，对每个顶点v，检查尾部为v的所有边。计算v的标签加上边的权重，得到一个值x（v肯定已经被标注了）。对于边的头顶点w，有两种可能：
w 没有标注。然后用值 x.
w
w 已标记。在这种情况下，比较x和w的标签。
- 如果相同，继续检查。
- 否则，您将得到一个边数最少的圆，因为您正在进行 BFS。立即停止。
当从v开始的所有边都被检查后，转到BFS中的下一个顶点。如果所有顶点都通过测试，则不存在该圆。
希望对您有所帮助！
我有一个连通图 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 到它自身的所有 paths/cycles 并检查它们是否全部加起来等于 0。我在以有效方式找到所有 paths/cycles 时遇到问题，是否有更优雅的解决方案，或者我应该尝试找到找到所有路径的最有效算法？
如果我没理解错的话，这个问题等同于"For a given vertex v, for any other vertex's, check if all paths from v to that vertex have a same weight"。
我想你可以通过 BFS 做到这一点，只需用与 v 的距离标记顶点，并检查遍历时是否有不同的距离。
换句话说，由于从起始顶点到某个顶点的所有距离都应该相同，因此您可以为每个顶点创建具有该距离的标签。从给定的起始顶点开始，BFS 遍历所有顶点的。遍历图时，对每个顶点v，检查尾部为v的所有边。计算v的标签加上边的权重，得到一个值x（v肯定已经被标注了）。对于边的头顶点w，有两种可能：
w没有标注。然后用值x. 标记 w已标记。在这种情况下，比较x和w的标签。- 如果相同，继续检查。
- 否则，您将得到一个边数最少的圆，因为您正在进行 BFS。立即停止。
w
当从v开始的所有边都被检查后，转到BFS中的下一个顶点。如果所有顶点都通过测试，则不存在该圆。
希望对您有所帮助！