networkx：高效地找到有向圖中絕對最長的路徑

我希望networkx在我的定向非循環圖中找到絕對最長的路徑。networkx：高效地找到有向圖中絕對最長的路徑

我知道Bellman-Ford，所以我否定了我的圖表長度。問題： networkx的bellman_ford（）需要源節點。我想從給定節點找到最長路徑（或否定之後的最短路徑），而不是最長路徑絕對。

當然，我可以在圖中的每個節點上運行bellman_ford（），然後排序，但是有沒有更高效的方法？

從我讀過的（例如， http://en.wikipedia.org/wiki/Longest_path_problem）我知道有實際上可能不是一個更有效的方法，但不知道是否任何人有任何想法（和/或已經證明P = NP（壞笑））。

編輯：我圖中的所有邊長都是+1（否定後爲-1），所以只需訪問大多數節點的方法也可以。一般來說，當然不可能訪問所有節點。

編輯：好的，我剛剛意識到我可以添加一個附加節點，只需連接到圖中的每個其他節點，然後從該節點運行bellman_ford。還有其他建議嗎？

來源

2013-08-01 barrycarter

有一個在http://en.wikipedia.org/wiki/Longest_path_problem

這裏提到的一個線性時間算法是一個（非常輕度測試）實施

EDIT，這顯然是錯誤的，見下文。 +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)

編輯前：修改後的版本（使用您自己的風險，並請報告bug）

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-01 15:14:57 Aric

這不是家庭作業。當然，networkx會實現這個算法？我試過你的鏈接，它似乎需要登錄？ – barrycarter

我更新了代碼。你是對的 - 那個環節不好。應該有其他參考 - 也許我們可以找到一個好的。 – Aric

事實證明，我的圖已經進行了拓撲排序，並且我可以根本不使用networkx來解決問題（通過跟蹤每個節點的最長傳入路徑和每個此類路徑的前一個節點，就像您指出的那樣）。簡直不敢相信！ – barrycarter

ARIC修訂後的答案是一個很好的，我發現它已經被networkx庫所採用link

但是，我發現這個方法有點缺陷。

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

因爲pairs是（int，nodetype）的元組列表。比較元組時，python會比較第一個元素，如果它們相同，則會處理以比較第二個元素，即nodetype。但是，在我的情況下，nodetype是一個自定義類，它沒有定義比較方法。因此蟒扔掉等的錯誤 '類型錯誤：unorderable類型：XXX（）> XXX（）'

對於可能改善，我說的線

dist[node] = max(pairs)

可以通過

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

被替換

對不起格式，因爲這是我第一次發佈。我希望我可以在阿里克的回答下面發表評論，但網站禁止我這樣說，我沒有足夠的聲譽（罰款...）

來源

2016-12-02 05:43:54

networkx：高效地找到有向圖中絕對最長的路徑

回答

相關問題