迪尼茨#

dinitz(G, s, t, capacity='capacity', residual=None, value_only=False, cutoff=None)[源代码]#

用迪尼茨算法求最大单个商品流。

此函数返回计算最大流量后产生的剩余网络。有关networkx用于定义剩余网络的约定的详细信息,请参阅下面的内容。

该算法的运行时间为 \(O(n^2 m)\)\(n\) 节点和 \(m\)[1].

参数
G网络X图表

图的边应该有一个称为‘Capacity’的属性。如果不存在该属性,则认为该边具有无限容量。

s结点

流的源节点。

t结点

流的汇聚节点。

capacity字符串

图G的边被期望具有指示该边可以支持多少流的属性容量。如果不存在该属性,则认为该边具有无限容量。默认值:‘Capacity’。

residual网络X图表

要在其上执行算法的剩余网络。如果没有,则创建新的剩余网络。默认值:无。

value_only布尔尔

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

cutoff整数、浮点数

如果指定,则当流量值达到或超过分界值时,算法将终止。在这种情况下,它可能无法立即确定最低降幅。默认值:无。

返回
R网络X有向图

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

加薪
NetworkXError

该算法不支持多重图和多重有向图。如果输入图形是这两个类之一的实例,则会引发NetworkXError。

NetworkXUnbounded

如果图有一条无限容量的路径,则图上的可行流的值在上面是无界的,并且该函数引发一个NetworkXUnbound。

笔记

剩余网络 R 从输入图 G 具有与相同的节点 G . R 是包含一对边的有向图 (u, v)(v, u) 敌我识别 (u, v) 不是自循环,并且至少是 (u, v)(v, u) 存在于 G .

对于每个边缘 (u, v) 在里面 RR[u][v]['capacity'] 等于 (u, v) 在里面 G 如果它存在于 G 否则为零。如果容量是无限的, R[u][v]['capacity'] 将具有不影响问题解的高任意有限值。此值存储在 R.graph['inf'] . 对于每个边缘 (u, v) 在里面 RR[u][v]['flow'] 表示的流函数 (u, v) 满足 R[u][v]['flow'] == -R[v][u]['flow'] .

流量值,定义为流入的总流量 t 水槽储存在 R.graph['flow_value'] .如果 cutoff 未指定,可访问到 t 仅使用边 (u, v) 这样的话 R[u][v]['flow'] < R[u][v]['capacity'] 诱导最小值 s -t 切。

工具书类

1

迪尼茨的算法:原始版本和Even的版本。2006年。叶菲姆·迪尼茨。理论计算机科学。计算机科学讲义。3895卷。第218-240页。Https://doi.org/10.1007/11685654_10

实例

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