CODEWITHSUNDEEP
algorithmgraph
haruhi93
haruhi93

Reputation: 11

Find a path with zero weight sum between two vertices

Given a weighted DAG with vertices u and v, each edge weight is either -1 or 1. How to determine whether there is a path from u to v with zero weight sum? I can only come up with an algorithm which is figuring out all paths from u to v and then sum up the weights to see if a path can satisfy the requirement. I've heard about A* approach for similar problems but I think this question should not be that complex. Is there a better algorithm for this problem?

Upvotes: 1

Views: 338

Answers (1)

chill
chill

Reputation: 16888

Consider the vertex u with successor nodes n_i, with respective edge weights w_i.

You have path with weight W from u to v if you have:

  • path from n_0 to v with weight W - w_0, or

  • path from n_1 to v with weight W - w_1, or

  • ...
  • etc

You can make a DP algorithm on the basis of the above, and memoizing subproblem solutions in the form of a set, containing <n,w> pairs, meaning "there's is a path from n to v with weight w." You have a solution if the set contains in the end <u,0>.

Upvotes: 3

Related Questions