max_flow_min_cost

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

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

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

参数:

GNetworkX 图

在其上查找满足所有需求的最小成本流的有向图。

s: 节点标签

流的源。

t: 节点标签

流的汇点。

capacity: 字符串

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

weight: 字符串

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

返回:

flowDict: 字典

按节点键入的字典的字典，其中 flowDict[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