图形中的最长路径

Question

给定一个顶点为0到n-1的无向图，编写一个函数，该函数将找到最长的路径（按边数计），该路径的顶点顺序递增。

您会建议采用哪种方法来解决这个难题？

Answer 1

我会做一个动态规划算法。将L ( u ) 表示为从节点u开始的最长有效路径。您的基本情况是L ( n -1) = [ n -1] （即仅包含节点n -1的路径）。然后，对于从n -2 到 0 的所有节点s ，从s开始执行 BFS ，其中只允许遍历边 ( u , v )，使得v > u。一旦你到达一个已经开始的节点（即，你已经计算出L ( u )的节点u），L ( s ) = 从s到u + L ( u ) 的最长路径所有可能的u > s。

问题的答案是具有最大值L ( u ) 的节点u，该算法为 O( E )，其中E是图中的边数。我认为你不能渐进地做得比这更快

编辑：实际上，“BFS”甚至不是 BFS：它只是遍历边缘（s，v）使得v > s（因为您已经访问了所有节点v > s，所以没有遍历：您将立即点击您已经开始的节点）

所以实际上，简化的算法是这样的：

longest_path_increasing_nodes():
    L = Hash Map whose keys are nodes and values are paths (list of nodes)
    L[n-1] = [n-1] # base case
    longest_path = L[n-1]
    for s from n-2 to 0: # recursive case
        L[s] = [s]
        for each edge (s,v):
            if v > s and length([s] + L[v]) > length(L[s]):
                L[s] = [s] + L[v]
        if length(L[s]) > length(longest_path):
            longest_path = L[s]
    return longest_path

编辑 2022-03-01：修复了最后一个 if 语句中的拼写错误；感谢用户650654！

Answer 2

通过将每个（无向）边替换为有向数较大的节点的有向边，可以将原始图转换为有向无环图。

然后，您最终得到以下结果：https : //www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/