埃德蒙兹-卡普算法

计算机科学中，埃德蒙兹-卡普算法通过实现福特-富尔克森算法来计算网络中的最大流，其时间复杂度为${\displaystyle O(VE^{2})}$。该算法由叶菲姆·迪尼茨在1970年最先提出，并由杰克·埃德蒙兹和理察德·卡普在1972年独立发表。^[1]

C++實作

以下是关于埃德蒙兹-卡普算法的C++语言描述：

struct Main {  struct Edge {  int u, v, Capacity, Flow;  Edge (int u, int v, int Capacity, int Flow) :  u(u), v(v), Capacity(Capacity), Flow(Flow) {}  };  struct Edmonds_Karp {  vector<Edge> Edges;  vector<int> Graph[MAXN]; // 保存下标  int n, Augment[MAXN], Previous[MAXN];  // 当起点到 Augment[i] 的可改进量；  void Initialise(int n)  {  for (int i = 0; i < n; ++i)  G[i].clear();  Edges.clear();  }  void Add(int u, int v, int Capacity)  {  Edges.push_back(Edge(u, v, Capacity, 0));  Edges.push_back(Edge(v, u, 0, 0));  int m = Edges.size() - 1;  Graph[u].push_back(m - 1);  Graph[v].push_back(m);  }  };  int MaxFlow(int s, int t)  {  int FlowSum = 0;  while (1) {  memset(Augment, 0, sizeof Augment);  queue<int> Travel;  Travel.push(s);  Augment[s] = INT_MAX;  while (!Travel.empty()) {  int From = Travel.front();  Travel.pop();  for (int i = 0; i < Graph[From].size(); ++i) {  Edge &Temp = Edges[Graph[From][i]];  if (!Augment[Temp.v] && Temp.Capacity > Temp.Flow) {  Previous[Temp.v] = Graph[From][i];  Augment[Temp.v] = min(Augment[From], Temp.Capacity - Temp.Flow);  Travel.push(Temp.v);  }  }  if (Augment[t]) break;  }  if (!Augment[t]) break;  for (int i = t; i != s; i = Edges[Previous[i]].From) {  Edges[Previous[i]].Flow += Augment[t];  Edges[Previous[i] ^ 1].Flow -= Augment[t];  }  FlowSum += Augment[t];  }  return flow;  }  Main(void) {} }; 

参考资料

1. Edmonds, Jack; Karp, Richard M. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (Association for Computing Machinery). 1972, 19 (2): 248–264. doi:10.1145/321694.321699 （英语）. 

参见

• 福特-富尔克森算法
• 迪尼茨算法
• 网络流