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

Question

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

6

我希望networkx能够找到有向无环图中的绝对最长路径。我知道Bellman-Ford算法，因此我将我的图长度取反。问题是：networkx的bellman_ford()需要一个源节点。我想找到绝对最长路径（或在取反后的情况下的最短路径），而不是从给定节点开始的最长路径。

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

根据我所读的（例如，http://en.wikipedia.org/wiki/Longest_path_problem），实际上可能没有更有效的方法，但我想知道是否有人有任何想法（和/或已经证明了P=NP（微笑））。

编辑：我图中的所有边长度都为+1（或在取反后为-1），因此简单地访问最多节点的方法也可以工作。通常，当然不可能访问所有节点。

编辑：好的，我刚意识到我可以添加一个额外的节点，将其与图中的每个其他节点连接起来，然后从该节点运行贝尔曼-福德算法。还有其他建议吗？

- user354134

2个回答

0

Aric的修订答案很好，我发现它已被networkx库link采用。

然而，我发现这种方法有一个小缺陷。

if pairs:
    dist[node] = max(pairs)
else:
    dist[node] = (0, node)

因为pairs是(int，nodetype)元组的列表。在比较元组时，Python会比较第一个元素，如果它们相同，则继续比较第二个元素，即nodetype。然而，在我的情况下，nodetype是一个自定义类，其比较方法未定义。因此，Python会抛出一个错误，如“TypeError：unorderable types: xxx() > xxx()”

为了可能的改进，我建议修改这行代码

dist[node] = max(pairs)

可以被替换为

dist[node] = max(pairs,key=lambda x:x[0])

很抱歉，由于这是我第一次发布，所以格式可能有些问题。我希望我可以像评论一样在Aric的回答下面发表我的看法，但是网站禁止我这样做，称我声望不够（好吧...）

- Shichu Zhu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aric · Accepted Answer

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

这里有一个（经过轻微测试的）实现。

编辑，这显然是错误的，请参见下文。在发布之前进行充分测试，未来请多加注意。

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)