從源節點上查找DAG上的最長路徑

我正試圖從頂點0中找到DAG的最長路徑。在Stackoverflow上搜索後，我明白我可以反轉邊緣的權重並使用Bellman Ford算法查找最長的路徑。但是，我不完全明白這是如何工作的。從源節點上查找DAG上的最長路徑

但是我的圖表沒有權重（都是相等的），我假設我應該設置爲-1？

我正在使用networkx和python來解決這個問題。這裏是我的貝爾曼代碼：

def Bellman(G): 
    pred, dist = nx.bellman_ford(G, 0, weight='-1') 
    print(dist)

不管我設置什麼重量，我仍然可以從0每個節點我要去哪裏錯了最低的距離是多少？

來源

2015-10-15 ForeverLearning

SO回答在http://stackoverflow.com/questions/17985202/networkx-efficiently-find-absolute-longest-path-in-digraph – Aric

@Aric這是絕對的圖中，我正在從一個特定的源節點。 – ForeverLearning

根據networkx documentation，bellamn_ford的權重參數是包含權重的邊緣屬性的關鍵。我想通過將其設置爲不存在的邊緣屬性'-1'，它不考慮任何權重。你將不得不做，以使這項工作是創建一個設置爲-1所有邊緣的邊緣屬性：

for n in G: 
    for nbr in G[n]: 
    G[n][nbr]['myWeight'] = -1

，然後使用貝爾曼 - 福特這個屬性作爲權重來電：

pred, dist = nx.bellman_ford(G, 0, weight='myWeight')

請注意，不要使用像'myWeight'這樣的「自定義」屬性，也可以將默認屬性'weight'設置爲-1，然後調用Bellman-Ford而不必明確指定權重參數。

來源

2015-10-15 08:58:31 matz

只是澄清：或者做G [n] [nbr] ['weight']而不是'myWeight'，以便您可以調用nx.bellman_ford（G，0）而不指定weight參數，因爲它是'weight'默認。或者你必須打電話如下：nx.bellman_ford（G，0，weight ='myWeight']） –

@AbdallahSobehy感謝你指出了這一點。我已將這個澄清納入答案。 – matz

@matz和我必須再次反演結果以獲得每個節點的實際長度是？ – ForeverLearning

從源節點上查找DAG上的最長路徑

回答

相關問題