给定有向无权图,问题是找到最大长度的简单路径(开始顶点和结束顶点不固定)。它显然可以在 O(n^2 * 2 ^n) 中解决,但我听说有 O(n * 2 ^ n) 算法我不知道。那么如何在 O(n * 2 ^n) 中解决呢?//n = |V|
问问题
2102 次
1 回答
5
如果您的问题确实是DAG上的最长路径问题,则来自 Wikipedia 的算法在下面并在 O(|V| + |E|) 中运行:
algorithm dag-longest-path is
input:
Directed acyclic graph G
output:
Length of the longest path
length_to = array with |V(G)| elements of type int with default value 0
for each vertex v in topOrder(G) do
for each edge (v, w) in E(G) do
if length_to[w] <= length_to[v] + weight(G,(v,w)) then
length_to[w] = length_to[v] + weight(G, (v,w))
return max(length_to[v] for v in V(G))
于 2010-11-29T02:22:22.280 回答