algorithm - 具有多个源顶点的边加权 DAG 中的最短路径？

Question

给定一个算法 A，它计算从具有非负边权重的 DAG G 中的源顶点 s 开始的最长路径。运行算法 A 以在 DAG G 中找到最长路径所需的最少次数是多少？

一种方法是找出多个源顶点，这可以在 O(|Edges|) 中实现。然后以这些顶点中的每一个作为源顶点运行算法 A。这将需要运行算法 A NumberOfSourceVertices 次。

我们能做得更好吗？

标签： algorithmgraph-algorithm

Answer 1

是的，我们可以做得更好。将新节点添加z到G. 对于每个已识别的源顶点s，将一条边(z, s, 0)（零边权重）添加到 G。

在修改后运行A 一次G。