如何使用Python NetworkX找到最長的路徑？

Question

我有一個從S到T的有向圖。

我想找到路徑（S，A，C，E，T）及其容量之和（1 + 2 + 3 + 1 = 7）所以總數是最大的。

我試過networkx.algorithms.flow.ford_fulkerson，但我不知道如何支持從S獲得單向方向T.

我的環境：

• 的Ubuntu 12.04
• 的Python 2.7.8
• NetworkX 1.9
• Matplotlib 1.4.0

example.py

#!/usr/bin/env python 
# -*- coding: utf-8 -*- 

import matplotlib.pylab as p 
import networkx as nx 

if __name__ == '__main__': 
    DG = nx.DiGraph() 
    DG.add_edge('S', 'a', capacity=1) 
    DG.add_edge('a', 'b', capacity=1) 
    DG.add_edge('a', 'c', capacity=2) 
    DG.add_edge('b', 'd', capacity=1) 
    DG.add_edge('b', 'e', capacity=2) 
    DG.add_edge('c', 'e', capacity=3) 
    DG.add_edge('c', 'f', capacity=2) 
    DG.add_edge('d', 'T', capacity=1) 
    DG.add_edge('e', 'T', capacity=1) 
    DG.add_edge('f', 'T', capacity=1) 

    result = nx.algorithms.flow.ford_fulkerson(DG, 'S', 'T') 
    print(result.size(weight='capacity')) # 15.0, but I want 7. 

    pos = nx.spectral_layout(DG) 
    nx.draw(DG, pos) 
    nx.draw_networkx_labels(DG, pos) 
    nx.draw_networkx_edge_labels(DG, pos) 
    p.show() 

    # This shows a partly bidirectional graph, which is not what I want. 
    pos = nx.spectral_layout(result) 
    nx.draw(result, pos) 
    nx.draw_networkx_labels(result, pos) 
    nx.draw_networkx_edge_labels(result, pos) 
    p.show() 

Answer 1

我想我找到了解決方案。

#!/usr/bin/env python 
# -*- coding: utf-8 -*- 

import networkx as nx 

def inverse_weight(graph, weight='weight'): 
    copy_graph = graph.copy() 
    for n, eds in copy_graph.adjacency_iter(): 
     for ed, eattr in eds.items(): 
      copy_graph[n][ed][weight] = eattr[weight] * -1 
    return copy_graph 

def longest_path_and_length(graph, s, t, weight='weight'): 
    i_w_graph = inverse_weight(graph, weight) 
    path = nx.dijkstra_path(i_w_graph, s, t) 
    length = nx.dijkstra_path_length(i_w_graph, s, t) * -1 
    return path, length 

if __name__ == '__main__': 
    DG = nx.DiGraph() 
    DG.add_edge('S', 'a', weight=1) 
    DG.add_edge('a', 'b', weight=1) 
    DG.add_edge('a', 'c', weight=2) 
    DG.add_edge('b', 'd', weight=1) 
    DG.add_edge('b', 'e', weight=2) 
    DG.add_edge('c', 'e', weight=3) 
    DG.add_edge('c', 'f', weight=2) 
    DG.add_edge('d', 'T', weight=1) 
    DG.add_edge('e', 'T', weight=1) 
    DG.add_edge('f', 'T', weight=1) 

    print(longest_path_and_length(DG, 'S', 'T')) # (['S', 'a', 'c', 'e', 'T'], 7) 

Answer 2

對於Dijkstra算法，使用負值通常不起作用。 將顯示此錯誤ValueError: ('Contradictory paths found:', 'negative weights?')。

它應該區分「最長路徑」和「最大和路徑」的問題。

答案在這裏：How to find path with highest sum in a weighted networkx graph?，它使用all_simple_paths。

請注意，在功能all_simple_paths(G, source, target, cutoff=None)中，使用cutoff參數（整數）可以幫助將搜索深度從source限制爲target。它還控制我們想要查找的路徑的長度。

Answer 3

負權重適用於johnson。在你的情況，修改爲：

DG = nx.DiGraph() 
DG.add_edge('S', 'a', weight=-1) 
DG.add_edge('a', 'b', weight=-1) 
DG.add_edge('a', 'c', weight=-2) 
DG.add_edge('b', 'd', weight=-1) 
DG.add_edge('b', 'e', weight=-2) 
DG.add_edge('c', 'e', weight=-3) 
DG.add_edge('c', 'f', weight=-2) 
DG.add_edge('d', 'T', weight=-1) 
DG.add_edge('e', 'T', weight=-1) 
DG.add_edge('f', 'T', weight=-1) 

爲了找到最長路徑，得到S中的單向方向

p2 = nx.johnson (DG, weight='weight') 
print('johnson: {0}'.format(p2['S']['T'])) 

結果爲T：johnson: ['S', 'a', 'c', 'e', 'T']

我的環境：

• 軟件版本
• Python 3.4.5 64位[MSC v.1600 64位（AMD64）]
• IPython的5.1.0 OS的Windows 10 10.0.14393
• networkx 1.11

Networkx 1.11 docs for johnson