在计算机科学中，Edmonds-Karp算法是用于在O（V E2）时间内计算流网络中的最大流量的Ford-Fulkerson方法的实现。 该算法最初由Yefim Dinitz于1970年出版，并由Jack Edmonds和Richard Karp于1972年独立出版。Dinic的算法包括将运行时间减少到O（V2 E）的其他技术。

该算法与Ford-Fulkerson算法相同，只是定义了找到增广路径时的搜索顺序。 找到的路径必须是具有可用容量的最短路径。 这可以通过广度优先搜索找到，其中我们对每个边缘应用1的权重。 通过显示每个增强路径可以在O（E）时间内找到O（V E2）的运行时间，每次E边缘中的至少一个变得饱和（具有最大可能流量的边缘）， 从增强路径到饱和边缘到源的距离必须比上次饱和的时间长，并且长度最多为V.该算法的另一个特性是最短增强路径的长度单调增加。 算法简介中有一个可访问的证明。

给定七个节点的网络，源A，接收器G和容量，如图1

在写在边上的f / c对中，f是电流，c是容量。 从u到v的剩余容量是c f（u，v）= c（u，v） - f（u，v），总容量减去已经使用的流量。 如果从u到v的净流量为负，则有助于剩余容量。

注意算法（红色）找到的增强路径的长度从未减少。 找到的路径是最短的。 找到的流量等于分隔源和汇的图中最小切割的容量。 此图中只有一个最小割，将节点划分为集合{A，B，C，E}和{D，F，G}，具有容量。

c（A，D）+ c（C，D）+ c（E，G）= 3 + 1 + 1 = 5。