迪尼茨#
- 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)
在里面R
,R[u][v]['capacity']
等于(u, v)
在里面G
如果它存在于G
否则为零。如果容量是无限的,R[u][v]['capacity']
将具有不影响问题解的高任意有限值。此值存储在R.graph['inf']
. 对于每个边缘(u, v)
在里面R
,R[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