max_flow_min_cost

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

返回一个最小成本的最大 (s, t)-流。

G 是一个带有边成本和容量的有向图。图中有一个源节点 s 和一个汇节点 t。此函数找到从 s 到 t 的最大流，其总成本最小。

Parameters:

GNetworkX 图

要在其上找到满足所有需求的最小成本流的 DiGraph。

s: 节点标签

流的源节点。

t: 节点标签

流的汇节点。

capacity: 字符串

图 G 的边应具有一个属性 capacity，指示该边可以支持多少流量。如果此属性不存在，则认为该边具有无限容量。默认值：’capacity’。

weight: 字符串

图 G 的边应具有一个属性 weight，指示在该边上发送一个单位的流量所产生的成本。如果不存在，则认为权重为 0。默认值：’weight’。

Returns:

flowDict: 字典

由节点键控的字典的字典，使得 flowDict[u][v] 是边 (u, v) 的流量。

Raises:

NetworkXError

如果输入图不是有向的或不连通，则引发此异常。

NetworkXUnbounded

如果 G 中存在从 s 到 t 的无限容量路径，则引发此异常。在这种情况下，没有最大流。如果有向图 G 具有负成本和无限容量的循环，也会引发此异常。在这种情况下，流成本无下界。

See also

cost_of_flow, min_cost_flow, min_cost_flow_cost, network_simplex

Notes

如果边权重或需求是浮点数，此算法不保证能正常工作（溢出和舍入误差可能导致问题）。作为一种解决方法，可以通过将相关边属性乘以一个方便的常数因子（例如 100）来使用整数。

Examples

>>> 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