在图中找到成本最高的路径的最佳方法

Question

我有一个有向无环图，每个顶点的权重 >= 0。有一个顶点是图的“开始”，另一个顶点是图的“结束”。这个想法是找到从起点到终点的路径，其中顶点的权重之和更大。例如，我有下一张图：

I(0) -> V1(3) -> F(0)
I(0) -> V1(3) -> V2(1) -> F(0)
I(0) -> V3(0.5) -> V2(1) -> F(0)

成本最高的路径是 I(0) -> V1(3) -> V2(1) -> F(0)，其成本为 4。

现在，我正在使用 BFS 枚举从 I 到 F 的每条路径，如上例所示，然后，我选择总和最大的那个。恐怕这种方法真的很幼稚。

有没有更好的算法来做到这一点？这个问题可以简化为另一个问题吗？

Answer 1

由于您的图没有循环^*，您可以否定边的权重，并运行贝尔曼-福特算法。

^*最短路径算法（例如Floyd-Warshall和 Bellman-Ford）不适用于具有负循环的图，因为您可以通过保持在负循环中来构建任意小权重的路径。