algorithm - push-relabel 最大流量算法是如何工作的？

Question

我阅读了 Wikipedia 和 TopCoder 上的相应文章，我读到的内容几乎没有任何意义。

编辑:在阅读幻灯片放映并更仔细地重新阅读 TopCoder 文章后，我仍然不明白何时以及如何进行重新标记。

Answer 1

为了理解推送-重新标记算法，您需要了解推送和重新标记操作。该算法只是在可能的时候迭代运行它们中的每一个。同样在某些时候，当算法执行通过网络的流程时，实际上并不是有效的——但会在最后。

推送(节点)

Push 检查进入节点的流量是否多于离开节点的流量，以及是否有一些多余的流量可能离开该节点(该节点的一些传出边中有剩余容量)

重新标记(节点) 这将进入一个无法离开的节点的多余流量，因为所有传出边都饱和了，并通过传入边向后传播，从而可以减少它们的流出。这通常是通过存储与每个节点关联的势能或高度来完成的，并且您确保流量总是沿着势能下降。