我们如何确定在 Ford-Fulkerson 中使用后向边缘的路径是有效的?

问题描述 投票:0回答:1

在用于在流网络中寻找最大流的福特富尔克森算法中,我们使用后向边缘,以便我们可以改进最大流(基本上改进已经选择的增广路径)。如果没有它,所选择的增强路径并不能保证它们能够最大化流量。

但我无法理解它为什么有效。我的意思是,为什么我们可以确定某些经过后向边缘的增广路径是可以在原始网络流中找到的路径(换句话说,为什么我们可以确定使用后向边缘的增广路径具有原始网络流中的表示形式)图形)?另外,为什么最大流量等于所有找到的增广路径的总和,而不仅仅是保证最大流量的路径?

algorithm graph-theory network-flow ford-fulkerson
1个回答
0
投票

直观地说,要找到最大流量,您需要将从起点流到终点的所有可能路径的所有可能容量相加。因此,Ford-Fulkerson,需要后向边缘,因为用于查找从起点到终点的路径的算法(BFS)不能保证最优,因为流路径可能会占用另一条路径到达终点的边缘容量点,这将限制计算最大流量的可能路径的数量。因此,创建后向边缘是为了保证另一条路径仍然可以到达终点。直观上可以理解为,在一个管道系统中,如果一条管道有水从两个方向(使用前缘和后缘)以相似的体积流量流入,它也会从两个相似体积流量的方向流出,从而呈现出路径无关,因为水基本上不移动,仍然会流向其他替代路径以到达终点

© www.soinside.com 2019 - 2024. All rights reserved.