flow - 基于福特富尔克森的算法会有死胡同吗？

Question

我们能否像我们在 dinics 算法中所做的那样，在ford fulkerson merhod 中移除那些在 DFS 期间不会导致下沉 t 的边？如果没有，请您举个例子。

Answer 1

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