networkx:有效地找到有向图中的绝对最长路径

Question

我希望 networkx 在我的定向中找到绝对最长的路径，
无环图。

我知道 Bellman-Ford，所以我否定了我的图长度。问题:
networkx 的 bellman_ford() 需要一个源节点。我想找到
绝对最长路径(或否定后的最短路径)，而不是
从给定节点的最长路径。

当然，我可以在图中的每个节点上运行 bellman_ford() 并且
排序，但有没有更有效的方法？

从我读过的(例如，
http://en.wikipedia.org/wiki/Longest_path_problem ) 我意识到那里
实际上可能不是更有效的方法，但想知道是否
任何人都有任何想法(和/或已经证明 P=NP(咧嘴笑))。

编辑:我图中的所有边长都是 +1(或否定后的 -1)，因此简单地访问最多节点的方法也可以工作。一般来说，当然不可能访问所有节点。

编辑:好的，我刚刚意识到我可以添加一个额外的节点，它只是连接到图中的每个其他节点，然后从该节点运行 bellman_ford。还有其他建议吗？

Answer 1

在 http://en.wikipedia.org/wiki/Longest_path_problem 中提到了一个线性时间算法。

这是一个(非常简单的测试)实现

编辑，这显然是错误的，见下文。 +1 以便在发布之前进行更多的测试

import networkx as nx

def longest_path(G):
    dist = {} # stores [node, distance] pair
    for node in nx.topological_sort(G):
        pairs = [[dist[v][0]+1,v] for v in G.pred[node]] # incoming pairs
        if pairs:
            dist[node] = max(pairs)
        else:
            dist[node] = (0, node)
    node, max_dist  = max(dist.items())
    path = [node]
    while node in dist:
        node, length = dist[node]
        path.append(node)
    return list(reversed(path))

if __name__=='__main__':
    G = nx.DiGraph()
    G.add_path([1,2,3,4])
    print longest_path(G)

编辑:更正版本(使用风险自负，请报告错误)

def longest_path(G):
    dist = {} # stores [node, distance] pair
    for node in nx.topological_sort(G):
        # pairs of dist,node for all incoming edges
        pairs = [(dist[v][0]+1,v) for v in G.pred[node]] 
        if pairs:
            dist[node] = max(pairs)
        else:
            dist[node] = (0, node)
    node,(length,_)  = max(dist.items(), key=lambda x:x[1])
    path = []
    while length > 0:
        path.append(node)
        length,node = dist[node]
    return list(reversed(path))

if __name__=='__main__':
    G = nx.DiGraph()
    G.add_path([1,2,3,4])
    G.add_path([1,20,30,31,32,4])
#    G.add_path([20,2,200,31])
    print longest_path(G)