首页 文章

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

提问于
浏览 次
5

我希望networkx在我的有向非循环图中找到绝对最长的路径 .

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

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

从我读过的内容（例如，http://en.wikipedia.org/wiki/Longest_path_problem）我意识到实际上可能没有更有效的方法，但是想知道是否有人有任何想法（和/或已证明P = NP（笑）） .

编辑：我的图中的所有边长都是1（或者在否定后为-1），因此只需访问大多数节点的方法也可以 . 通常，当然不可能访问所有节点 .

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

networkx

2 回答

  • 0

    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)
    回复于
  • 4

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

    但是，我发现这种方法存在一些缺陷 .

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

    因为pair是（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的回答下面发表评论作为评论，但该网站禁止我这样做，说明我没有足够的声誉（好......）

    回复于

相关问题