Edmonds–Karp algorithm

The Edmonds - Karp algorithm is in computer science and graph theory, an implementation of the Ford - Fulkerson method for computing the maximum st- flow in networks with positive real capacities. It uses the respective shortest augmenting path in each step, which ensures that the algorithm terminates in polynomial time.

In most implementations, the shortest path is determined by a breadth-first search, which leads to a term in. The algorithm was first published in 1970 by the Russian scientist EA Dinic and later independently by Jack Edmonds and Richard M. Karp, who published it in 1972, discovered. Dinics algorithm includes additional techniques to reduce the run time.