最短增广路径#
- shortest_augmenting_path(G, s, t, capacity='capacity', residual=None, value_only=False, two_phase=False, cutoff=None)[source]#
使用最短增广路径算法寻找最大单商品流。
该函数返回计算最大流后得到的残差网络。关于 NetworkX 定义残差网络的约定，请参阅下文详情。
该算法对于 \(n\) 个节点和 \(m\) 条边的图，运行时间复杂度为 \(O(n^2 m)\)。
- 参数:
- GNetworkX 图
图的边应具有名为 ‘capacity’ 的属性。如果此属性不存在，则认为该边的容量是无限的。
- s节点
流的源节点。
- t节点
流的汇节点。
- capacity字符串
图 G 的边应具有 capacity 属性，指示该边可以支持的流量。如果此属性不存在，则认为该边的容量是无限的。默认值：‘capacity’。
- residualNetworkX 图
执行算法所基于的残差网络。如果为 None，则会创建一个新的残差网络。默认值：None。
- value_only布尔值
如果为 True，则仅计算最大流的值。该算法将忽略此参数，因为它不适用。
- two_phase布尔值
如果为 True，则使用两阶段变体。两阶段变体将单位容量网络的运行时间从 \(O(nm)\) 改进到 \(O(\min(n^{2/3}, m^{1/2}) m)\)。默认值：False。
- cutoff整数，浮点数
如果指定，当流值达到或超过 cutoff 时，算法将终止。在这种情况下，可能无法立即确定最小割。默认值：None。
- 返回:
- RNetworkX 有向图
计算最大流后的残差网络。
- 抛出:
- NetworkXError
该算法不支持 MultiGraph 和 MultiDiGraph。如果输入图是这两个类之一的实例，则会抛出 NetworkXError。
- NetworkXUnbounded
如果图存在无限容量的路径，则图上的可行流值无上界，函数会抛出 NetworkXUnbounded。
注意
输入图
G的残差网络R与G拥有相同的节点。当且仅当(u, v)不是自环且(u, v)和(v, u)中至少有一条边存在于G中时，R是一个包含边对(u, v)和(v, u)的有向图。对于
R中的每条边(u, v)，R[u][v]['capacity']等于它在G中的容量（如果存在），否则为零。如果容量是无限的，R[u][v]['capacity']将是一个高任意有限值，不影响问题的解。该值存储在R.graph['inf']中。对于R中的每条边(u, v)，R[u][v]['flow']表示(u, v)的流函数，并满足R[u][v]['flow'] == -R[v][u]['flow']。流值定义为流入汇点
t的总流量，存储在R.graph['flow_value']中。如果未指定cutoff，则仅使用满足R[u][v]['flow'] < R[u][v]['capacity']的边(u, v)到达t，这会诱导一个最小的s-t割。示例
>>> 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