Python NetworkX max_flow_min_cost 函数永远运行

Question

我试图在某些图表上使用 max_flow_min_cost，但有时算法似乎会永远运行(或至少运行很长时间)，我不明白为什么会这样。这是导致它运行那么长时间的图表。它们都有相同的节点

nodes = [
    ('1in', {'y': -1, 'x': -1, 'type': 'passenger in', 'number': 1}), 
    ('2out', {'y': 1, 'x': -1, 'type': 'passenger out', 'number': 2}),
    ('destination', {'y': 0, 'x': 0, 'type': 'destination'}), 
    ('2in', {'y': 1, 'x': -1, 'type': 'passenger in', 'number': 2}),
    ('source', {'type': 'meta'}), 
    ('4in', {'y': -1, 'x': 1, 'type': 'passenger in', 'number': 4}),
    ('1out', {'y': -1, 'x': -1, 'type': 'passenger out', 'number': 1}),
    ('4out', {'y': -1, 'x': 1, 'type': 'passenger out', 'number': 4}),
    ('sink', {'type': 'meta'}), 
    ('3in', {'y': 1, 'x': 1, 'type': 'passenger in', 'number': 3}),
    ('3out', {'y': 1, 'x': 1, 'type': 'passenger out', 'number': 3})
]

edges = [
    ('1in', '1out', {'cost': 0, 'capacity': 1}), 
    ('2out', '4in', {'cost': -9.48, 'capacity': 1}), 
    ('2out', 'destination', {'cost': -10.9, 'capacity': 1}), 
    ('2out', '3in', {'cost': -10.31, 'capacity': 1}), 
    ('destination', 'sink', {'cost': 0, 'capacity': 1}), 
    ('2in', '2out', {'cost': 0, 'capacity': 1}), 
    ('source', '2in', {'cost': 0, 'capacity': 1}), 
    ('source', '4in', {'cost': 0, 'capacity': 1}), 
    ('source', '1in', {'cost': 0, 'capacity': 1}), 
    ('source', '3in', {'cost': 0, 'capacity': 1}), 
    ('4in', '4out', {'cost': 0, 'capacity': 1}), 
    ('1out', '2in', {'cost': -10.31, 'capacity': 1}), 
    ('1out', '4in', {'cost': -10.31, 'capacity': 1}), 
    ('1out', 'destination', {'cost':-10.9, 'capacity': 1}), 
    ('1out', '3in', {'cost': -9.48, 'capacity': 1}), 
    ('4out', 'destination', {'cost': -10.9, 'capacity': 1}), 
    ('3in', '3out', {'cost': 0, 'capacity': 1}), 
    ('3out', '4in', {'cost': -10.31, 'capacity': 1}), 
    ('3out', 'destination', {'cost': -10.9, 'capacity': 1})
]

如果我修改上图，但使从目的地到接收器的容量为 2 或 3，它也会永远运行。如果我使容量等于 4，算法运行良好。这是确切的调用:

nx.max_flow_min_cost(G,'source','sink',weight='cost')

谢谢!任何帮助将不胜感激。值得一提的是，G是一个有向图(DiGraph)

编辑:我opened an issue在 NetworkX 项目上，以防他们的代码出现问题。

Answer 1

如果权重是 float ，则不能保证 networkx.max_flow_min_cost 中的算法有效。在此处的 networkx 网站上查看原始作者的问题回答

https://github.com/networkx/networkx/issues/2076#issuecomment-210200259