网络流算法: 最大流算法

网络流算法是一类用于解决在流网络中最大化流从源点到汇点问题的算法. 流网络是由节点和有向边构成的图, 每条边有一个容量限制, 表示可以通过该边的最大流量. 网络流问题的目标是找到一种流分配方式, 使得整个网络从源到汇的总流量最大.

在下图中, 节点 0 是源点, 节点 5 是汇点, 最大流问题就是求从源点到汇点的最大流量是多少.

下面是一种可行的解决方案. 路径权重中, 前者表示实际通过的流量, 后者表示其最大容量.

Ford-Fulkerson 方法

Ford-Fulkerson 方法是一种用于解决最大流问题的经典算法, 它通过寻找增广路径(augmenting path)来逐步增加网络中从源点到汇点的流量, 直到无法再找到新的增广路径为止. 这种方法基于的是残量图和增广路径的概念.

残量图(Residual Graph)

残量图是从从网络流的状态衍生出来的. 它给每条边增加了反向边. 每个边的权重会重新调整: 假设其原来最大容量为 $a$, 当前流量为$b$, 则参量图中这个边的最大容量为 $a-b$, 反向边的流量为 $b$.

以下图为例, 这是一个原始图. 此时没有流量.

下图中, 左侧是当前的流量状态, 而右侧则是残量图的状态.

我们可以看到:

• 对于 (0 -> 1) 这条边, 总容量为3,目前容量为3. 所以在残量图中: (0 -> 1) 的最大容量为 $3-3=0$, 反向边(1 - > 0)的容量为 $3$.
• 对于 (1 -> 2) 这条边, 总容量为5, 当前流量为3. 所以在残量图中: (1 -> 2) 的最大容量为 $5-3=2$, 反向边(2 - > 1)的容量为 $3$.

数学表述为: 给定一个流网络 $G=(V,E)$ 以及其上的流 $f$, 残量图 $Gf$ 包含了原网络中的每条边, 同时也包括了反向边. 对于原网络中的每条边 $(u,v)$, 如果当前流 $f(u,v)$ 小于容量 $c(u,v)$, 则在残量图中存在一条从 $u$ 到 $v$ 的边, 容量为 $c_f(u,v)=c(u,v)-f(u,v)$; 同时, 如果 $f(u,v)>0$, 则在残量图中也存在一条从 $v$ 到 $u$ 的边, 容量为 $c_f(v,u)=f(u,v)$.

增广路径

在残量图中, 从源 s 到汇 t 的一条路径被称为增广路径, 如果这条路径上所有的边都具有正容量. 沿着这样的路径可以增加流值, 增加量由路径上最小剩余容量决定.

继续以上图为例, 我们可以在参量图中寻找从源点到汇点的路径. 如图, 我们发现了一条:

可以看到这条路径可以通过的最大流量为2. 所以我们可以获得2的增量. 对应的流量图为右侧图所示.

Edmonds-Karp 算法

Edmonds-Karp算法是Ford-Fulkerson方法的一种实现, 用于计算网络流图中的最大流. 它特别之处在于使用广度优先搜索(BFS)来寻找增广路径, 即从源节点到汇节点的最短路径(这里的最短是指路径上的边数最少). 这保证了算法的效率和稳定性, 并且使得其时间复杂度为O(VE^2), 其中V是网络中的顶点数, E是边数.

算法步骤

1. 初始化: 开始时, 所有边的流量都设为0.
2. 寻找增广路径: 通过BFS寻找从源到汇的最短路径, 这条路径上所有的边必须有剩余容量(即实际容量大于当前流量).
3. 更新流量: 一旦找到增广路径, 就沿着这条路径增加流量, 直到无法再找到增广路径为止.
4. 终止条件: 当没有从源到汇的增广路径时, 算法终止, 此时的流量即为最大流.

Edmonds-Karp算法相比于其他实现Ford-Fulkerson方法的变种更加稳定, 因为它总是选择最短的增广路径, 这避免了某些情况下可能出现的低效行为. 此外, 由于其清晰的步骤和逻辑, 它也是学习网络流问题的良好起点.

代码实现

构建残量图

void BuildResidualGraph() {
  residual_graph_.Reset(graph_.V(), graph_.Directed(), graph_.Weighted());
  for (Vertex u = 0; u < graph_.V(); u++) {
    for (Vertex v : graph_.Adj(u)) {
      residual_graph_.AddEdge(u, v, graph_.GetWeight(u, v));
      residual_graph_.AddEdge(v, u, 0);
    }
  }
}

寻找增广路径

std::vector<WeightedEdge> FindArgumentPath(const AdjList& graph, unsigned src,
                                            unsigned dst) {
  std::vector<unsigned> parent(graph.V(), UINT_MAX);
  std::vector<bool> visited(graph.V(), false);

  std::queue<unsigned> q;
  q.push(src);
  while (!q.empty()) {
    auto curr = q.front();
    q.pop();

    if (curr == dst) break;
    if (visited[curr]) continue;
    visited[curr] = true;

    for (auto w : graph.Adj(curr)) {
      if (visited[w]) continue;
      if (graph.GetWeight(curr, w) <= 0) continue;
      parent[w] = curr;
      q.push(w);
    }
  }
  std::vector<WeightedEdge> path;
  if (parent[dst] == UINT_MAX) return path;
  int curr = dst;
  while (parent[curr] != src) {
    auto begin = parent[curr];
    auto end = curr;
    auto weight = graph.GetWeight(begin, end);
    path.emplace_back(begin, end, weight);
    curr = begin;
  }
  path.emplace_back(src, curr, graph.GetWeight(src, curr));
  std::reverse(path.begin(), path.end());
  return path;
}

Edmonds-Karp算法主程序

int MaxFlow(unsigned source, unsigned sink) {
  BuildResidualGraph();

  int max_flow = 0;
  while (true) {
    auto path = FindArgumentPath(residual_graph_, source, sink);
    fmt::println("path: {}\n", fmt::join(path, ","));

    if (path.empty()) break;
    auto it = std::min_element(path.begin(), path.end(),
                                [](const auto& lhs, const auto& rhs) {
                                  return std::get<2>(lhs) < std::get<2>(rhs);
                                });
    auto flow = std::get<2>(*it);
    max_flow += flow;

    for (auto& [u, v, w] : path) {
      residual_graph_.UpdateWeight(u, v, -flow);
      residual_graph_.UpdateWeight(v, u, flow);
    }
  }
  return max_flow;
}

完整代码请参考: EdmondsKarp.ixx

Edmonds-Karp Demo

std::vector<graph::WeightedEdge> edges = {
    std::make_tuple(0, 1, 3), std::make_tuple(0, 2, 2),
    std::make_tuple(1, 2, 5), std::make_tuple(1, 3, 2),
    std::make_tuple(2, 3, 3),
};
graph::AdjList wg(4, edges, true);
graph::EdmondsKarp ek(wg);
auto len = ek.MaxFlow(0, 3);
std::cout << "max flow: " << len << "\n";
std::cout << ek.ResidualGraph();

完整代码参考: MaxFlowDemo.cpp