未加权图中的最大流量

Question

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

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

Answer 1

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

重新表述一下你的问题，当每条边的容量为 1 时，是否存在一种更简单的算法来解决最大流问题？

这实际上取决于您所说的“更简单”的含义，但是您可以使用Ford-Fulkerson 算法在时间限制内解决这种特殊情况O(VE)，这比使用上述时间限制为 的 Edmonds-Karp 算法解决它要快得多O(VE^2)。