algorithm - 为什么在 Edmonds Karp 算法中使用 BFS 以使其与 Ford Fulkerson 更好？

Question

因为，当我在上面研究 Edmonds Karp 算法时，它指出 Edmonds Karp 使用 BFS，因此复杂度不取决于流量值，但我无法理解，BFS 如何帮助？

标签： algorithmgraph-theorybreadth-first-search

Answer 1

非正式地，当 E-K 沿路径推动流时，路径中的每个节点都比其前身离源更远（其中距离是相对于残差弧的未加权图定义的）。关键不变量是没有节点更接近源。作为 F-F 的一个实例，E-K 使路径上的一条弧饱和，其尾部在某个距离 d 处，其头部在距离 d+1 处。为了使这条弧再次成为残差，我们必须在反向弧上推动流动，这需要尾部移动到距离 d+2。|V|-1 的距离有一个上限，所以这不可能发生任意次数，就像 F-F 具有非理性权重一样。随后的 push-relabel 算法通过不每次都从头开始重新计算最短路径距离来扩展这种直觉。

（有人告诉我 CLRS 有正式的证明。）