基于Ford-fulkerson的算法会有死胡同吗

Question

我们能像在dinics算法中那样，在ford-fulkerson-merhod中删除那些在DFS过程中不会导致下沉t的边吗？如果没有，你能举个例子吗。

Answer 1

明白了。因为在ford-fulkerson中，我们可以使用通过反向边缘的增强路径来减少正向边缘流，这可能会使正向边缘在DFS的下一次迭代中可用。因此，去除边缘不是一个好主意。而在dinic中，死的v一旦死了就不能再使用了，因为没有反向边，离开v的边流就不可能减少。