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

Question

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

Answer 1

这可以通过动态编程类算法来解决。

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

让我们来源。设置Fs [0] = 0，并且所有其他Fs [i] = - 无穷大。

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

现在，

为每个节点V，执行以下更新：

的Fv [I] = MAX {的Fv [I]，FW [I-1] +成本（W，V ）|其中w为v的邻居}

重复上面的至少X次的更新，然后检查的Fv [X]所有v到得到你想要的最大值。

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

以上算法是Bellman-Ford Algorithm的特殊情况

Answer 2

您可以使用Bellman-Ford algorithm来做你想做的。