min_cost_flow_cost

min_cost_flow_cost(G, demand='demand', capacity='capacity', weight='weight')

在有向图G中找到满足所有需求的最小成本流的成本。

G是一个有向图，具有边缘成本和容量，其中节点有需求，即它们希望发送或接收一定数量的流。负需求意味着节点想要发送流，正需求意味着节点想要接收流。如果流入每个节点的净流量等于该节点的需求，则有向图G上的流量满足所有需求。

参数

G网络X图表

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

demand字符串

图G的节点预期具有属性Demand，该属性指示节点想要发送(负需求)或接收(正需求)多少流。注意需求的总和应该是0，否则问题就不可行。如果该属性不存在，则节点被视为具有0需求。默认值：‘Demand’。

capacity字符串

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

weight字符串

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

返回

flowCost整数、浮点数

满足所有需求的最小成本流的成本。

加薪

NetworkXError

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

NetworkXUnfeasible

在以下情况下会引发此异常：

• 这些要求的总和不是零。那么，就没有满足所有需求的流了。

• 没有能满足所有需求的流量。

NetworkXUnbounded

如果有向图G有一个负成本和无限容量的圈，则会引发这个例外。然后，满足所有需求的流的成本在下面是无界的。

参见

cost_of_flow, max_flow_min_cost, min_cost_flow, network_simplex

笔记

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

实例

最小成本流问题的一个简单例子。

>>> G = nx.DiGraph()
>>> G.add_node("a", demand=-5)
>>> G.add_node("d", demand=5)
>>> G.add_edge("a", "b", weight=3, capacity=4)
>>> G.add_edge("a", "c", weight=6, capacity=10)
>>> G.add_edge("b", "d", weight=1, capacity=9)
>>> G.add_edge("c", "d", weight=2, capacity=5)
>>> flowCost = nx.min_cost_flow_cost(G)
>>> flowCost
24