6

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

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

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

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

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

编辑：好的，我刚刚意识到我可以添加一个简单地连接到图中每个其他节点的附加节点，然后从该节点运行 bellman_ford。还有其他建议吗？

4

2 回答 2

4

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)
于 2013-08-01T15:14:57.780 回答
0

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

但是，我发现这种方法有一点缺陷。

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 的答案下方发表评论，但网站禁止我这样做，说我没有足够的声誉（很好......）

于 2016-12-02T05:43:54.450 回答