有向未加权图中最长的非循环path
什么algorithm可以用来find未加权的有向无环图中最长的path？
dynamic编程 。 最长path问题也被引用，因为它是一个DAG。
以下代码来自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)) 只要图是非循环的，你所要做的就是取消边权值并运行任何最短pathalgorithm。
编辑：显然，你需要一个支持负权重的最短pathalgorithm。 此外，维基百科的algorithm似乎有更好的时间复杂性，但我会留下我的答案在这里作为参考。
维基百科有一个algorithm： http : //en.wikipedia.org/wiki/Longest_path_problem
看起来他们使用权重，但应该与权重都设置为1。
可以通过关键path方法解决：
1.find一个拓扑顺序
2.find关键path
参见[Horowitz 1995]，C ++数据结构基础，计算机科学出版社，纽约。
贪婪的策略（例如Dijkstra）不会工作，不pipe：1。 使用“最大”而不是“最小”2.将正面权重转换为负面3.给出非常大的数字M，并使用Mw作为权重。
