从DAG中的某些节点源之间的最长路径 [英] Longest path between from a source to certain nodes in a DAG

问题描述

我如何找到所有的最终目的地，从单一来源的最长路径 即对于源I1，提供最长路径I1之间 - > O1和I1 - > O2

How do i find the longest path from single source to all final destinations i.e. For source i1, Give longest path between i1 -> o1 and i1 -> o2.

在上图描述的图例如下：  （I1，I2）是启动节点  （O1，O2）是末端节点  （1-8）是子图  边缘可有+香港专业教育学院/ -ive权

The legends described in the above graph are as follows: (i1, i2) are start nodes (o1, o2) are end nodes (1-8) are sub graphs The edges may have +ive/-ive weights

在此网络中最长的路径是按以下顺序：

The longest paths in this network are in the following order:

最糟糕的路径：I1 - > 1 - > 4 - > 01

Worst path: i1 -> 1 -> 4 -> o1

然后，所有的路径I1 ... - > ... 01

Then, all paths i1 … -> … o1

然后I1 - > 5 - > 6 - > O2

Then i1 -> 5 -> 6 -> o2

需要一种方法来忽略选择（I1 - > 3）或（3 - > 4）子网络，即使他们长于I1 - > 5

Need a way to ignore selection of (i1 -> 3) or (3 -> 4) subnetworks even though they are longer than i1 -> 5

推荐答案

维基百科救援！他们对这个问题的页面显示，在一般情况下，你的问题是NP完全问题。不过，既然你已经定向的无环的图，可以颠倒所有的边权重并运行的 Bellman-Ford算法​​来解决它。对BF算法通常计算单源最短路径中的曲线图。随着倒边的权重，它应该产生最长的路径。

Wikipedia to the rescue! Their page on this problem indicates that in the general case, your problem is NP-Complete. However, since you have a directed acyclic graph, you can invert all the edge weights and run the Bellman-Ford algorithm to solve it. The B-F algorithm normally computes single-source shortest paths in a graph. With inverted edge weights, it should produce the longest paths.

这篇关于从DAG中的某些节点源之间的最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！