network_simplex#

network_simplex(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整数, 浮点数

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

flowDict字典

以节点为键的字典的字典，其中 flowDict[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. Efficient implementation of minimum-cost flow algorithms. Acta Universitatis Sapientiae, Informatica 4(1):67–118. 2012.

[2]

R. Barr, F. Glover, D. Klingman. Enhancement of spanning tree labeling procedures for network optimization. INFOR 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': {}}
在本页