algorithm - 多个目的地的最高加权路径

Question

我有一个有向循环加权图。我想找到一条权重最高的路径，长度为 X 个顶点，我不在乎目的地是什么。我只想找到最高的成本。

Answer 1

这可以通过类似动态规划的算法来解决。

由于您只有几百个节点，而 X 是第 10 轮。您可以为每个节点 v 分配一个大小为 X 的数组 Fv，Fv[i] 表示从源到长度为 i 的节点 v 的最大成本。

让我们成为源。设置 Fs[0] = 0，所有其他 Fs[i] = -infinity。

所有其他数组都初始化为-infinity数组。

现在，

对于每个节点 v，执行以下更新：

Fv[i] = max{Fv[i], Fw[i-1] + 成本(w, v) | 其中 w 是 v 的邻居}

重复上述更新至少 X 次，然后检查所有 v 的 Fv[X] 以获得您想要的最大可能值。

您可以使用一些额外的信息来检索路径，这应该很容易做到。

上述算法是Bellman-Ford 算法的一个特例

Answer 2

你可以使用Bellman-Ford 算法来做你想做的事。