min_cost_flow_cost#

min_cost_flow_cost(G, demand='demand', capacity='capacity', weight='weight')[source]#

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

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

参数:
GNetworkX 图

寻找满足所有需求的最小成本流的有向图。

demand字符串

图 G 的节点应具有一个名为 demand 的属性，表示节点希望发送（负需求）或接收（正需求）多少流量。请注意，所有需求的总和应为 0，否则问题将不可行。如果此属性不存在，则认为节点的需示为 0。默认值：'demand'。

capacity字符串

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

weight字符串

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

返回:
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
在本页