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

示例.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

使用负权重通常不适用于 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 参数(整数)可以帮助限制搜索深度从源到目标。它还控制我们要查找的路径的长度。