图表中最长的路径

Question

给定一个顶点形式为0到n-1的无向图，写一个函数，找到最长的路径（按边数），哪个顶点构成一个递增的序列。

你会推荐什么样的方法来解决这个难题？

Answer 1

您可以将原始图形转换为有向非循环图形，方法是将每个（无向）边缘替换为朝向具有较大数字的节点的有向边缘。

然后你最终得到这个：https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

Answer 2

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

问题的答案是节点u的最大值为L（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 L[s] > longest_path:
            longest_path = L[s]
    return longest_path

Answer 3

有像Dijkstra算法这样的算法可以修改以找到最长而不是最短的路径。

这是一个简单的方法：

• 使用递归算法查找2个节点之间的所有路径。
• 选择最长的路径。

如果您需要有关递归算法的帮助，请询问。