多汇、单源最大流量问题的迪尼克算法

Question

我正在尝试实现一种算法，该算法可以找到两个水槽，使来自给定源的总流量最大。我正在使用Dinic的算法，并在很大程度上基于此版本的实现，并具有适当的驱动程序函数:

def maxflow( G,s ):
g = Graph( G )
maximum=0
for i in range( g.V ):
g.addEdge( ( i, g.V-1, float('inf') ) )
g2 = copy.deepcopy( g )
for j in range(g2.V):
if j == i or j == s or i==s:
continue
g2.addEdge( ( j, g.V-1, float('inf') ) )
maximum = max( g2.DinicMaxflow( s, g.V-1 ), maximum )
g2 = copy.deepcopy( g )
g.removeVirtualSink(i)
return maximum

据我所知，除了检查每个可能的顶点对之外，真的没有更好的方法来做这件事。我遇到的问题是，由于算法留下了残差矩阵，我需要一种方法来存储一个"默认值"。状态，这样我就可以在每次DinicMaxflow()调用后返回到它，但是deepcopy()非常慢。是否有一种方法可以更快地复制数据，或者最好使其使我不必在每次函数调用后复制数据?

Answer 1

我也遇到了同样的问题，我想出了一个解决方案:其中u制作一个额外的节点:将其连接到所有具有无限流量范围的开始节点，并将其视为开始节点。在接收器中，同样的情况下，连接到一个额外的节点，将其连接到所有以前的接收器节点，并将此新节点视为最终接收器。Dinic的算法已经很复杂了，而多个start和sink又增加了复杂度。所以这个技巧可能会有所帮助。我测试了这个实现，并且总是有效。祝你过得愉快。