最大路径问题

发布于 2024-10-05 02:10:29 字数 129 浏览 5 评论 0 原文

给定有向无权图，问题是找到最大长度的简单路径（起始顶点和结束顶点不固定）。显然可以在 O(n^2 * 2 ^n) 中解决，但我听说有 O(n * 2 ^ n) 算法，我不知道。那么如何在 O(n * 2 ^n) 内解决呢？ //n = |V|

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

年华零落成诗 2024-10-12 02:10:29

如果您的问题确实是最长路径问题 .wikipedia.org/wiki/Directed_acirclic_graph" rel="noreferrer">DAG，来自维基百科的算法如下，运行时间为 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))

If your problem really is the Longest Path Problem on a DAG, the algorithm from Wikipedia is below and runs in 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))

回复收藏 0 原文

~没有更多了~