algorithm - 找到两个顶点之间权重和为零的路径

Question

给定一个带顶点 u 和 v 的加权 DAG，每条边的权重要么为 -1 要么为 1。如何确定是否存在从 u 到 v 的路径且权重和为零？我只能想出一个算法，计算出从u到v的所有路径，然后将权重相加，看看是否有一条路径可以满足要求。我听说过类似问题的 A* 方法，但我认为这个问题不应该那么复杂。这个问题有更好的算法吗？

Answer 1

考虑顶点 u有后继节点 n_i , 具有各自的边权重 w_i .

您的路径权重为 W，来自 u至 v如果你有:

• 来自 n_0 的路径至 v有重量W - w_0 ，或者

• 来自 n_1 的路径至 v有重量W - w_1 , 或

• ...
• 等等

可以在上面的基础上做一个DP算法，以集合的形式内存子问题的解，包含<n,w>对，意思是“有一条从 n 到 v 的路径，权重为 w 。”如果集合最后包含 <u,0>，您就有解决方案.