基于Ford fulkerson的算法中是否会有死胡同？

Question

我们是否可以像在dinics算法中一样去除那些在福特富尔克森方法中在DFS期间不会导致沉陷的边缘？如果没有，请您举个例子。

Answer 1

知道了。因为在福特福尔克森（Ford fulkerson）中，我们可以使用穿过反向边缘的增强路径来减少前向边缘流，这可能会使前向边缘在DFS的下一次迭代中可用。因此，删除边缘不是一个好主意。在dinic中，死的v一旦死了就无法再次使用，因为没有反向边缘的缘故，没有机会减少远离v的边流。