dinitz

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

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

此函数返回计算最大流后得到的残差网络。有关NetworkX用于定义残差网络的约定详情，请参阅下文。

对于\(n\)个节点和\(m\)条边，此算法的运行时间为\(O(n^2 m)\) [1]。

参数:

GNetworkX图

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

s节点

流的源节点。

t节点

流的汇节点。

capacity字符串

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

residualNetworkX图

要执行算法的残差网络。如果为None，则创建新的残差网络。默认值：None。

value_only布尔值

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

cutoff整数，浮点数

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

返回:

RNetworkX有向图

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

引发:

NetworkXError

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

NetworkXUnbounded

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

另请参阅

maximum_flow()

minimum_cut()

preflow_push()

shortest_augmenting_path()

注意

输入图G的残差网络R与G具有相同的节点。R是一个有向图，当且仅当(u, v)不是自环，并且G中至少存在(u, v)或(v, u)之一时，R包含一对边(u, v)和(v, u)。

对于R中的每条边(u, v)，R[u][v]['capacity']等于G中(u, v)的容量（如果存在于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']的边到t的可达性将导出一个最小s-t割。

参考文献

[1]

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

示例

>>> from networkx.algorithms.flow import dinitz

实现流算法并输出残差网络的函数（例如此函数）未导入到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 = dinitz(G, "x", "y")
>>> flow_value = nx.maximum_flow_value(G, "x", "y")
>>> flow_value
3.0
>>> flow_value == R.graph["flow_value"]
True