max_flow_min_cost

max_flow_min_cost(G, s, t, capacity='capacity', weight='weight')

返回最小成本的最大（s，t）流。

G是一个具有边缘成本和容量的有向图。有一个源节点S和一个接收节点T。此函数查找从S到T的最大流量，其总成本最小。

参数

G网络X图表

能找到满足所有要求的最小费用流的有向图。

s: node label

流的来源。

t: node label

流的目标。

capacity: string

图G的边被期望具有指示该边可以支持多少流的属性容量。如果不存在该属性，则认为该边具有无限容量。默认值：‘Capacity’。

weight: string

图G的边预期具有属性权重，该属性权重指示在该边上发送一个单元流所产生的成本。如果不存在，则认为权重为0。缺省值：‘权重’。

返回

Flow Dict：词典

以节点为关键字的字典的字典，如Flow Dict [u] [v] 是流动边(u，v)。

加薪

NetworkXError

如果输入图形未定向或未连接，则会引发此异常。

NetworkXUnbounded

如果G中存在从s到t的无限容量路径，则会引发此异常。在这种情况下，没有最大流量。如果有向图G有一个负成本和无限容量的圈，也会出现这种例外情况。然后，一个流的成本在下面是无界的。

参见

cost_of_flow, min_cost_flow, min_cost_flow_cost, network_simplex

笔记

如果边缘权重或需求是浮点数（溢出和舍入错误可能导致问题），则该算法无法保证工作。作为解决方法，您可以使用整数，方法是将相关的边缘属性乘以一个方便的常量因子（例如100）。

实例

>>> G = nx.DiGraph()
>>> G.add_edges_from(
...     [
...         (1, 2, {"capacity": 12, "weight": 4}),
...         (1, 3, {"capacity": 20, "weight": 6}),
...         (2, 3, {"capacity": 6, "weight": -3}),
...         (2, 6, {"capacity": 14, "weight": 1}),
...         (3, 4, {"weight": 9}),
...         (3, 5, {"capacity": 10, "weight": 5}),
...         (4, 2, {"capacity": 19, "weight": 13}),
...         (4, 5, {"capacity": 4, "weight": 0}),
...         (5, 7, {"capacity": 28, "weight": 2}),
...         (6, 5, {"capacity": 11, "weight": 1}),
...         (6, 7, {"weight": 8}),
...         (7, 4, {"capacity": 6, "weight": 6}),
...     ]
... )
>>> mincostFlow = nx.max_flow_min_cost(G, 1, 7)
>>> mincost = nx.cost_of_flow(G, mincostFlow)
>>> mincost
373
>>> from networkx.algorithms.flow import maximum_flow
>>> maxFlow = maximum_flow(G, 1, 7)[1]
>>> nx.cost_of_flow(G, maxFlow) >= mincost
True
>>> mincostFlowValue = sum((mincostFlow[u][7] for u in G.predecessors(7))) - sum(
...     (mincostFlow[7][v] for v in G.successors(7))
... )
>>> mincostFlowValue == nx.maximum_flow_value(G, 1, 7)
True