检查权重不等于0的周期 [英] Check for cycles whose weights don't sum up to 0

问题描述

我有一个连接图 g ，其中 n 顶点和 m 边缘。

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

因此，对于每一条边 u - > v 加权 w 存在一个边 v - > u c $ c> -w 。

我的目标：

对于给定的顶点 v ，检查是否存在回到 v （一个循环）的路径该路径的边权重总和不等于 0 。如果存在这样的路径，那么输出这样的路径的最小数量的边缘，否则输出所有的周期都可以。。

示例：

从 v 到 v 总计为 0 。输出为all cycles are fine：

一个例子，其中存在从 v 到 v 的路径边的总和不等于 0 。在这个例子中，这样一条路径的最小边数为4：

我目前的做法：

查找顶点 v 自己并检查它们是否总和为 0 。我有问题找到所有路径/周期有效的方式，有没有更优雅的解决方案，或者我应该尝试找到找到所有路径的最有效的算法？

解决方案

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

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

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

1. w 未标记。然后使用值 x 标记 w 。

2. 
   

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

   
   
   • 如果它们相同，请继续检查。
   
   
   • 否则，由于您正在执行BFS，因此您有一个边数最少的圆。立即停止。
   
   

当所有从 v 被选中，转到BFS中的下一个顶点。如果所有顶点都通过了测试，则不存在此类圆圈。

希望这有助于您！

I have a connected graph g with n vertices and m edges.

Each edge can be traversed from both directions, while traversing them in one direction their weight is positive, traverse them in the other direction and their weight is negative.

So for every edge u -> v with weight w there exists an edge v -> u with weight -w.

My goal:

For a given vertex v, check if there exists a path back to v (a cycle) so that the sum of the edge weights of that path is not equal to 0. If such a path exists then output the minimal number of edges of such a path, otherwise output "all cycles are fine".

Examples:

An example where all paths from v to v sum up to 0. The output is "all cycles are fine":

An example where there exist paths from v to v whose edges sum up to something which isn't equal to 0. The minimal number of edges of such a path is 4 in this example:

My current approach:

Find all paths/cycles from vertex v to itself and check if all of them sum up to 0. I have problems finding all paths/cycles in an efficient manner, is there a more elegant solution or should I try to find the most efficient algorithm for finding all paths?

解决方案

If I understand you correctly, this problem is equivalent to "For a given vertex v, for any other vertex's, check if all paths from v to that vertex have a same weight".

I guess you can do that by BFS, just mark vertex's with the distance from v, and check if there's different distance when traversing.

In other words, since all the distances from the starting vertex to a certain vertex should be the same, you can just create labels with that distance for each vertex. From the given starting vertex, BFS traverse all the vertex's. For each vertex v when you traverse the graph, check all the edge whose tail is v. Calculate the label of v plus the weight of the edge and get a value x (v must have been labeled). For the head vertex w of the edge, there is two possibility:

1. w is not labeled. Then label w with value x.

2. w has been labeled. In this case, compare x and the label of w.

   • If they are the same, continue checking.
   • Otherwise, you have a circle with minimal number of edges, since you are doing a BFS. Stop immediately.

When all the edges starting from v is checked, go to the next vertex in BFS. If all vertex has passed the test, no such circle exists.

Hope this helps!

这篇关于检查权重不等于0的周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！