Solve Longest Path Problem in linear time

We know that the longest path problem for general case belongs to the NP-hard category, so there is no known polynomial time solution for it. However, for a special case which is directed acyclic graph, we can solve this problem in linear time.

First, take a look at an algorithm that sloves the shortest path problem for DAG in linear time, which makes use of Topological sort.

Solve Longest Path Problem in linear time

Solve Longest Path Problem in linear time

Solve Longest Path Problem in linear time

The only modificaiton to negate the weight of all edges before running this algorithm in order for it to compute a longest path. This algorithm runs in O(V + E) time, its limitation is that it does not allow cycles in the graph.

上一篇:安装mysql5.5.28的步骤 2017.6.27


下一篇:获取父iframe的高宽