Check for cycles whose weights don't sum up to 0

3
votes

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":

Example 1

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:

Example 2

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?

1
javaalgorithmgraphgraph-algorithm

1 Answers

3
votes

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!