shortest_augmenting_path#

shortest_augmenting_path(G, s, t, capacity='capacity', residual=None, value_only=False, two_phase=False, cutoff=None)[source]#

使用最短增广路径算法寻找最大单商品流。

该函数返回在计算最大流后得到的残余网络。有关NetworkX定义残余网络的约定，请参见下文详细信息。

该算法对于:math:n`个节点和:math:`m`条边的时间复杂度为:math:`O(n^2 m)。

Parameters:
GNetworkX图

图的边应具有名为’capacity’的属性。如果该属性不存在，则认为该边具有无限容量。

s节点

流的源节点。

t节点

流的汇节点。

capacity字符串

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

residualNetworkX图

要在其上执行算法的残余网络。如果为None，则创建一个新的残余网络。默认值：None。

value_only布尔值

如果为True，仅计算最大流的值。该参数将被此算法忽略，因为它不适用。

two_phase布尔值

如果为True，则使用两阶段变体。两阶段变体在单位容量网络上将运行时间从:math:O(nm)`改进为:math:`O(min(n^{2/3}, m^{1/2}) m)。默认值：False。

cutoff整数, 浮点数

如果指定，当流值达到或超过cutoff时，算法将终止。在这种情况下，可能无法立即确定最小割。默认值：None。

Returns:
RNetworkX有向图

计算最大流后的残余网络。

Raises:
NetworkXError

该算法不支持MultiGraph和MultiDiGraph。如果输入图是这两个类之一的实例，则引发NetworkXError。

NetworkXUnbounded

如果图具有无限容量的路径，则图上可行流的价值无界，函数引发NetworkXUnbounded。

See also

maximum_flow()
minimum_cut()
edmonds_karp()
preflow_push()

Notes

从输入图:samp:G 得到的残余网络:samp:R 具有与:samp:G 相同的节点。R 是一个有向图，如果:samp:(u, v) 不是自环，并且:samp:G 中至少存在:samp:(u, v) 和:samp:(v, u) 之一，则:samp:R 包含一对边:samp:(u, v) 和:samp:(v, u) 。

对于:samp:R 中的每条边:samp:(u, v) ，R[u][v]['capacity'] 等于:samp:G 中:samp:(u, v) 的容量（如果存在）或零。如果容量是无限的，R[u][v]['capacity'] 将具有一个不影响问题解决方案的高任意有限值。该值存储在:samp:R.graph['inf'] 中。对于:samp:R 中的每条边:samp:(u, v) ，R[u][v]['flow'] 表示:samp:(u, v) 的流函数，并满足:samp:R[u][v]['flow'] == -R[v][u]['flow'] 。

流值，定义为流入汇:samp:t 的总流量，存储在:samp:R.graph['flow_value'] 中。如果未指定:samp:cutoff ，则仅使用满足:samp:R[u][v]['flow'] < R[u][v]['capacity'] 的边:samp:(u, v) 可达:samp:t ，诱导出最小:samp:s -t 割。

Examples

>>> from networkx.algorithms.flow import shortest_augmenting_path

实现流算法并输出残余网络的函数（如本函数）不会导入到NetworkX基础命名空间中，因此您必须从flow包中显式导入它们。

>>> G = nx.DiGraph()
>>> G.add_edge("x", "a", capacity=3.0)
>>> G.add_edge("x", "b", capacity=1.0)
>>> G.add_edge("a", "c", capacity=3.0)
>>> G.add_edge("b", "c", capacity=5.0)
>>> G.add_edge("b", "d", capacity=4.0)
>>> G.add_edge("d", "e", capacity=2.0)
>>> G.add_edge("c", "y", capacity=2.0)
>>> G.add_edge("e", "y", capacity=3.0)
>>> R = shortest_augmenting_path(G, "x", "y")
>>> flow_value = nx.maximum_flow_value(G, "x", "y")
>>> flow_value
3.0
>>> flow_value == R.graph["flow_value"]
True
On this page