Clever Geek Handbook

Check cycles that do not add up to 0

I have a connected graph g

with vertices n

and m

edges.

Each edge can go in both directions, and when you move them in one direction, their weight is positive, cross them in the other direction and their weight is negative.

So, for each edge u

→ v

with a weight, w

there is an edge v

→ u

with a weight -w

.

My goal:

For a given vertex, v

check if there is a path back to v

(loop), so the sum of the weights of that path is not equal 0

. If such a path exists, print the minimum number of edges of such a path, otherwise print "all cycles are fine"

.

<strong> Examples:

An example where all paths from v

to v

are summed to 0

. Output signal "all cycles are fine"

:

Example 1

An example where there are paths from v

to v

, whose edges add up to something that is not equal 0

. The minimum number of edges for such a path in this example is 4:

Example 2

My current approach:

Find all paths / loops from vertex v

to itself and check if they all add up to 0

. I am having trouble finding all paths / loops in an efficient way, is there a more elegant solution or should I try to find the most efficient all paths algorithm?

+3


source to share


1 answer


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

I think you can do this with BFS, just mark the vertex with a distance from v and check if the distance was different when passing.

In other words, since all distances from the starting vertex to a specific vertex must be the same, you can simply create labels with that distance for each vertex. From a given initial vertex, the BFS intersects all vertices. For each vertex v

as you cross the graph, check all the edges that have a tail v

. Calculate the label v

plus the edge weight and get the value x

( v

should be flagged). There w

are two possibilities for the top apex of an edge:



  • w

    not flagged. Then mark with a w

    value x

    .

  • w

    ... In this case, compare the x

    label as well w

    .

    • If they match, continue checking.
    • Otherwise, you have a circle with as few edges as you are doing BFS. Stop immediately.

When all edges starting with v

are marked, move on to the next vertex in the BFS. If all vertices pass the test, such a circle does not exist.

Hope this helps!

+3


source






More articles:


All Articles