min_cost_flow#

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

返回一个满足有向图 G 中所有需求的最低成本流。

G 是一个带有边成本和容量以及节点需求的有向图，即节点希望发送或接收一定量的流。负需求表示节点希望发送流，正需求表示节点希望接收流。如果每个节点的净流入量等于该节点的需求，则有向图 G 上的流满足所有需求。

Parameters:
GNetworkX 图

要在其上找到满足所有需求的最低成本流的有向图。

demand字符串

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

capacity字符串

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

weight字符串

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

Returns:
flowDict字典

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

Raises:
NetworkXError

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

NetworkXUnfeasible

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

  • 需求的总和不为零。那么，没有满足所有需求的流。

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

NetworkXUnbounded

如果有向图 G 具有负成本和无限容量的循环，则引发此异常。那么，满足所有需求的流的成本是无界的。

See also

cost_of_flow, max_flow_min_cost, min_cost_flow_cost, network_simplex

Notes

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

Examples

一个简单的最低成本流问题示例。

>>> 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)
>>> flowDict = nx.min_cost_flow(G)
>>> flowDict
{'a': {'b': 4, 'c': 1}, 'd': {}, 'b': {'d': 4}, 'c': {'d': 1}}
On this page