寻找有向图中节点数量最多的路径

Question

如何在有向图中找到节点数最多的路径呢？

我想我可以遍历每一个节点并深度搜索，以找出哪个路径具有最多的节点数，但我想知道是否有更好的方法。

注意：该图保证没有循环。

- Mihai Bişog

---

你的意思是你想要一个解决最长路径问题的算法吗？ - Fred Foo

你的图是一棵树。嗯，几乎是... :) - Michael Nett

Answer 1

你有一张有向无环图（DAG），想要找到包含节点最多的路径。实际上，这就是在DAG中找到最长路径。对于DAG，这个问题可以在多项式时间内解决。在这里阅读更多信息：维基百科。

- Priyank Bhatnagar

---

谢谢你的提示。最终我使用 Floyd-Warshall 算法解决了它，其中每条边的权重为-1。 - Mihai Bişog

Answer 2

如果图中有环，则存在“无限长”的路径。

如果图是无环的： 您应该运行拓扑排序。然后：

foreach(node in topological_sort_order) {
   foreach(prev_node in neibhours[node]) {
      // there is edge from prev_node to node
      // since vertices are sorted in topological order than
      // value for longest_path[prev_node] is already computed
      longest_path[node] = max(longest_path[node],  longest_path[prev_node] + 1);
   }
}

- Jarosław Gomułka

Answer 3

由于您的输入是有向图而不是有向无环图，因此它是NP-完全问题，所提到的解决方案不起作用。但正如logic_max所说：这是最长路径问题，您可以通过为每条边赋予成本一来减少它。

- AJed