如何用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

负权重在约翰逊算法中是可以使用的。在你的情况下，可以这样修改：

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 到 T 的单向方向，使用

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

结果是：johnson: ['S', 'a', 'c', 'e', 'T']

我的环境：

• 软件版本
• Python 3.4.5 64位 [MSC v.1600 64位 (AMD64)]
• IPython 5.1.0 操作系统 Windows 10 10.0.14393
• networkx 1.11

Networkx 1.11 的约翰逊算法文档

Networkx 3.21 的约翰逊算法文档

Answer 3

使用负权重通常不适合Dijkstra算法。这样会出现一个错误：ValueError: ('Contradictory paths found:', 'negative weights?')。

这里需要区分“最长路径”和“最大和路径”这两个问题。

这里的答案是：如何在加权的networkx图中找到和最大的路径？，这个答案使用了all_simple_paths。

注意，在函数all_simple_paths(G, source, target, cutoff=None)中，使用cutoff参数（一个整数）可以帮助限制从source到target的搜索深度。它还控制我们想要找到的路径的长度。