非赋权图中的最大流

Question

最大流问题通常采用edmond-karp算法来解决，该算法建立残差图，并利用BFS来寻找增广路径。

但最大流问题通常是针对赋权图定义的。对于未加权的图，我们可以简单地将每条边的权重视为1，但我想知道是否有更简单的算法来解决未加权的版本。

Answer 1

通常，人们在谈论流量问题时指的是边缘“容量”，在谈论距离相关问题时指的是“权重/成本”。这就减少了混淆。

换句话说，当每条边的容量都为1时，有没有更简单的算法来解决最大流问题？

这真的取决于你所说的“更简单”是什么意思，但你可以在O(VE)时间范围内使用Ford-Fulkerson algorithm来解决这种特殊情况，这比前面提到的埃德蒙兹-卡普算法在O(VE^2)时间范围内求解要快得多。