有向无权图中的最长无环路径 [英] 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.

以下代码来自维基百科:

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屋！