algorithm - 图 - 在具有正节点和负边的图形中移动的算法

Question

我有一个图表，节点中有一些正值，边缘中有一些负值。
我必须在图中精确地移动 x 次，从源节点到目标节点，目标是最大化总和:

• 当我停留在一个节点中进行移动时
• 通过边时的减法

所以，如果我在同一个节点停留移动，总和会增加，所以如果我在值为 10 的节点停留 4 次，我总共获得 40。下图是一个示例。

在这种情况下最好的解决办法是:

Move1 -> (源节点+3) 3

移动 2 -> (3-20+15) -2

Move3 -> (stay +15) 13

...(保持相同的节点)...

Move19 -> (stay +15) 253

Move20 -> (目的节点253-5+3) 251

什么是解决问题的有效方法？我可以实现伪代码之类的东西，只是为了了解如何解决它。

非常感谢。

Answer 1

这可以通过 Bellman-Ford algorithm 的变体来解决。 ，具有 O(|E|*n) 时间复杂度，其中 |E| 是边数，n 是步数:

为简单起见，假设您在每个节点中也有一个自循环，权重为 0，这表示“停留操作”。所以你有:

for all u in V:
(u,u) in E
w(u,u) = 0

现在，使用 Dynamic Programming 应用递归公式:

D[v][0] = 0          if v is the source
          -infinity  otherwise
D[v][i] = max { D[u][i-1] + w(u,v) + cost(v) | where (u,v) is an edge }

解决方案是D[target][n]

这基本上是 Bellman-Ford 算法(使用 max 而不是 min)，但是你在 n 迭代之后而不是在 之后停止>|V|.