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 长

score 4 · Accepted Answer

维基百科来拯救！他们关于这个问题的页面表明，在一般情况下，您的问题是 NP-Complete。但是，由于您有一个有向无环图，您可以反转所有边权重并运行Bellman-Ford 算法来解决它。BF 算法通常计算图中的单源最短路径。使用倒置的边缘权重，它应该产生最长的路径。

score 0 · Accepted Answer

我相信以下将为您提供到达目的地的最大步数（不是实际路径，只是步数）。这没有考虑边缘权重。这通过合并节点来工作，src直到除了目标节点之外没有邻居。

longestPath (src, dest) =
    if (neighbors(src) == [dest]) then 1
    else 1 + longestPath(newNode(concat (map neighbors (neighbors src))), dest)

2 回答 2