network_simplex#

network_simplex(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整数、浮点数: 满足所有需求的最小成本流的成本。
flowDict词典: 以节点为关键字的字典的字典，如Flow Dict [u] [v] 是流动边(u，v)。

加薪

NetworkXError

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

NetworkXUnfeasible

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

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

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

NetworkXUnbounded

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

参见

cost_of_flow, max_flow_min_cost, min_cost_flow, min_cost_flow_cost

笔记

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

工具书类

1: Z.Kiraly，P.Kovacs。有效实施最低成本流算法。萨皮蒂大学学报，信息学4（1）：67-118。2012。
2: R.Barr、F.Glover、D.Klingman。网络优化的生成树标记程序的增强。信息17（1）：16-34。1979。

实例

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

>>> 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, flowDict = nx.network_simplex(G)
>>> flowCost
24
>>> flowDict
{'a': {'b': 4, 'c': 1}, 'd': {}, 'b': {'d': 4}, 'c': {'d': 1}}

最小成本流算法也可以用来解决最短路径问题。为了找到两个节点u和v之间的最短路径，给所有边一个无限的容量，给节点u一个-1的需求，给节点v一个1的需求。然后运行网络单工。最小成本流的值将是U和V之间的距离，带正流的边将指示路径。

>>> G = nx.DiGraph()
>>> G.add_weighted_edges_from(
...     [
...         ("s", "u", 10),
...         ("s", "x", 5),
...         ("u", "v", 1),
...         ("u", "x", 2),
...         ("v", "y", 1),
...         ("x", "u", 3),
...         ("x", "v", 5),
...         ("x", "y", 2),
...         ("y", "s", 7),
...         ("y", "v", 6),
...     ]
... )
>>> G.add_node("s", demand=-1)
>>> G.add_node("v", demand=1)
>>> flowCost, flowDict = nx.network_simplex(G)
>>> flowCost == nx.shortest_path_length(G, "s", "v", weight="weight")
True
>>> sorted([(u, v) for u in flowDict for v in flowDict[u] if flowDict[u][v] > 0])
[('s', 'x'), ('u', 'v'), ('x', 'u')]
>>> nx.shortest_path(G, "s", "v", weight="weight")
['s', 'x', 'u', 'v']

可以更改算法所用属性的名称。

>>> G = nx.DiGraph()
>>> G.add_node("p", spam=-4)
>>> G.add_node("q", spam=2)
>>> G.add_node("a", spam=-2)
>>> G.add_node("d", spam=-1)
>>> G.add_node("t", spam=2)
>>> G.add_node("w", spam=3)
>>> G.add_edge("p", "q", cost=7, vacancies=5)
>>> G.add_edge("p", "a", cost=1, vacancies=4)
>>> G.add_edge("q", "d", cost=2, vacancies=3)
>>> G.add_edge("t", "q", cost=1, vacancies=2)
>>> G.add_edge("a", "t", cost=2, vacancies=4)
>>> G.add_edge("d", "w", cost=3, vacancies=4)
>>> G.add_edge("t", "w", cost=4, vacancies=1)
>>> flowCost, flowDict = nx.network_simplex(
...     G, demand="spam", capacity="vacancies", weight="cost"
... )
>>> flowCost
37
>>> flowDict
{'p': {'q': 2, 'a': 2}, 'q': {'d': 1}, 'a': {'t': 4}, 'd': {'w': 2}, 't': {'q': 1, 'w': 1}, 'w': {}}