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)