具有单位容量边的流网络中 Ford-Fulkerson 方法的时间复杂度
Time complexity of the Ford-Fulkerson method in a flow network with unit capacity edges
Ford-Fulkerson 算法能否在 O(mn) 时间内找到具有 n 个顶点和 m 条边的单位容量流量网络（所有边都具有单位容量）的最大流量？
O(M*f) 是 Ford-Fulkerson 在具有整数容量的图上的已知 运行 时间估计，其中 M 是边数，f 的值最大流量，只是因为很容易在每个 O(M) 中找到增广路径，并且每个这样的路径都会将流量至少增加 1.
如果你的图没有重复的边（即没有一对边具有相同的起始和结束顶点），并且每条边都有单位容量，那么最大流量f是不超过顶点的数量 N（只是因为从源开始的边不超过 N-1），因此复杂度确实是 O(N*M).
但是，如果您的图允许有重复的边（但每条边的容量仍然为 1），则 f 可以大于 N，最多 M，时间复杂度可以变成O(M*M)，不难举出发生这种复杂度的例子
Ford-Fulkerson 算法能否在 O(mn) 时间内找到具有 n 个顶点和 m 条边的单位容量流量网络（所有边都具有单位容量）的最大流量？
O(M*f) 是 Ford-Fulkerson 在具有整数容量的图上的已知 运行 时间估计，其中 M 是边数，f 的值最大流量，只是因为很容易在每个 O(M) 中找到增广路径，并且每个这样的路径都会将流量至少增加 1.
如果你的图没有重复的边（即没有一对边具有相同的起始和结束顶点），并且每条边都有单位容量，那么最大流量f是不超过顶点的数量 N（只是因为从源开始的边不超过 N-1），因此复杂度确实是 O(N*M).
但是，如果您的图允许有重复的边（但每条边的容量仍然为 1），则 f 可以大于 N，最多 M，时间复杂度可以变成O(M*M)，不难举出发生这种复杂度的例子