min_cost_flow#

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

返回满足有向图 G 中所有需求的最小费用流。

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

参数:
GNetworkX 图

在此有向图上寻找满足所有需求的最小费用流。

demand字符串

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

capacity字符串

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

weight字符串

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

返回值:
flowDict字典

一个以节点为键的字典，其中 flowDict[u][v] 表示边 (u, v) 上的流量。

引发异常:
NetworkXError

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

NetworkXUnfeasible

在以下情况下引发此异常

  • 需求的总和不为零。此时，没有流可以满足所有需求。

  • 没有流可以满足所有需求。

NetworkXUnbounded

如果有向图 G 存在具有负费用和无限容量的环，则引发此异常。此时，满足所有需求的流的费用无下界。

另请参阅

cost_of_flow, max_flow_min_cost, min_cost_flow_cost, 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)
>>> flowDict = nx.min_cost_flow(G)
>>> flowDict
{'a': {'b': 4, 'c': 1}, 'd': {}, 'b': {'d': 4}, 'c': {'d': 1}}
在此页面上