在一个有向非加权曲线最长非循环路径 [英] Longest acyclic path in a directed unweighted graph

问题描述

什么算法可以被用来找到在未加权向无环图的最长路径？

What algorithm can be used to find the longest path in an unweighted directed acyclic graph?

推荐答案

动态规划。它也被引用在最长路径问题的，因为它是一个DAG

Dynamic programming. It is also referenced in Longest path problem, given that it is a DAG.

这是维基百科以下code：

The following code from Wikipedia:

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))

这篇关于在一个有向非加权曲线最长非循环路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！