有序图伪代码中的最长路径

Question

我尝试创建一种算法来查找有序图中的最长路径。有序图的属性是：

每条边从索引较低的节点到索引较高的节点。也就是说，每条有向边都具有 (v_i, v_j) 的形式，其中 i < j.
除了v_n之外的每个节点至少有一条边离开它。也就是说，对于每个节点 v_i，至少有一个形式的边 (v_i, v_j).

我的第一次尝试如下：

set w = v1 and L = 0
While there is edge that leaves from w
    Choose the edge (w, vj) with j as small as possible
    set w = vj and L = L + 1
return L

我不明白为什么这个算法在某些情况下是错误的。能举个例子吗？

Answer 1

我的直觉告诉我，只选择最小的 j 并不意味着在其他地方j 将继续是最小的。

假设您有一个图 1-> 3 和 1 -> 5，但是 3 -> 9 和 5 -> 7 -> 9，其中 9 是最后一个节点。您的算法将 1 -> 3 -> 9 比 1 -> 5 -> 7 -> 9.

短

事实上，我不认为你真的可以只 "pick" 一个分支并继续跟踪它到底并且在任何情况下都是正确的：你必须检查其他分支。

递归方法

这是一种使用简单递归算法的方法，在每个分支处计算路径的长度，然后在有多个分支的节点处计算最长的 return。

简单的伪代码示例（采用Python的风格）

class node:
    def longest_path(self):
        if len(self.children) == 0: # No children in this node
            return 1
        child_lengths = []
        for child in self.children:
            child_lengths.append(child.longest_path())
        return max(child_lengths) + 1

有序图伪代码中的最长路径

Longest path in ordered graph pseudocode

algorithm

graph

pseudocode

greedy

递归方法