algorithm - 无法理解用于几何约束求解的伪代码最大流算法

Question

所以我正在努力解决 this paper ，这主要是关于找到加权图的最小密集子图(在几何约束求解的上下文中)。

稠密子图是边权重之和与顶点权重之和相等的子图。

作者解释说，这在某种程度上等同于最大流算法，因此他提出了标准最大流算法的变体，他说这种算法对于这个问题更有效。但是我对这些概念不太熟悉，而且我发现实际描述非常晦涩。也许有人可以帮我解决这个问题？

算法表述如下:

我对第 17 步应该是什么、流程实际初始化的位置以及增强过程的工作方式感到非常困惑。

论文提供了一个例子:

因此，我尝试逐步执行该示例，但我无法让它执行预期的操作。好像第一次循环时，它访问了 e1、v0 和 v2，并标记了 e0 和 e2。然后它访问 e0 并标记为 v2。然后它访问 e2，但是它的所有顶点都已经被访问过，所以该算法什么都不做。它如何增加路径？

提前致谢。

Answer 1

流实际初始化的地方它们不是 – 作者的疏忽。假设对于所有 e 和 v，f_e^v 最初为零。

增强过程的工作原理 第 17 步明显高于例程的其余部分。增广路径是最大流的标准子主题，许多本科算法课本都涵盖了这一主题。

让我们考虑一个所有权重都为 1 的流问题。

a-->b
   ^
  /
 /
c-->d

我还没有绘制s和t。假设我们已将一个单元从 c 推到 b。

a-->b
   /
  /
 v
c-->d

从 b 到 c 的反向弧出现是因为，虽然我们不能将流从 b 发送到 c 在绝对意义上，我们可以取消从 c 到 b 的一个单元，这在数学上具有相同的效果。最大流的值为 2，我们通过增加路径 a -> b -> c -> d 来实现。这只是意味着从 a 推一个单元到 b，从 c 取消一个单元到 b，推一个单位从 c 到 d。

这是第 17 步的一些伪代码。

Augment(vert, pred, amount)
  v = vert
  while true
    e = pred(v)
    f_e^v += amount
    if pred(e) is null
      break
    v = pred(e)
    f_e^v -= amount

amount 应该是不会导致任何边产生超过其权重或任何顶点消耗超过其权重的最大值。