algorithm - 从源到 DAG 中某些节点之间的最长路径

Question

我如何找到从单一来源到所有最终目的地的最长路径即对于源 i1，给出 i1 -> o1 和 i1 -> o2 之间的最长路径。

上图描述的图例如下: (i1, i2) 是起始节点 (o1, o2) 是端节点 (1-8) 是子图 边缘可能有 +ive/-ive 权重

此网络中最长的路径按以下顺序排列:

最坏路径:i1 -> 1 -> 4 -> o1

然后，所有路径 i1 … -> … o1

然后 i1 -> 5 -> 6 -> o2

需要一种方法来忽略对 (i1 -> 3) 或 (3 -> 4) 子网的选择，即使它们比 i1 -> 5 长

Answer 1

Wikipedia救援!他们关于这个问题的页面表明，在一般情况下，您的问题是 NP-Complete。然而，由于您有一个有向无环图，您可以反转所有边权重并运行 Bellman-Ford algorithm解决它。 B-F 算法通常计算图中的单源最短路径。使用反向边权重，它应该产生最长的路径。