dinitz

dinitz(G, s, t, capacity='capacity', residual=None, value_only=False, cutoff=None)

使用Dinitz算法寻找最大单商品流。

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

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

Parameters:

GNetworkX图

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

s节点

流的源节点。

t节点

流的汇节点。

capacity字符串

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

residualNetworkX图

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

value_only布尔值

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

cutoff整数, 浮点数

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

Returns:

RNetworkX有向图

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

Raises:

NetworkXError

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

NetworkXUnbounded

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

See also

maximum_flow()

minimum_cut()

preflow_push()

shortest_augmenting_path()

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 割。

References

[1]

Dinitz算法：原始版本和Even版本。 2006年。Yefim Dinitz。在理论计算机科学中。计算机科学讲义。第3895卷。第218-240页。 https://doi.org/10.1007/11685654_10

Examples

>>> from networkx.algorithms.flow import dinitz

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

>>> 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 = dinitz(G, "x", "y")
>>> flow_value = nx.maximum_flow_value(G, "x", "y")
>>> flow_value
3.0
>>> flow_value == R.graph["flow_value"]
True