Edmonds and Karp's algorithm

from Wikipedia, the free encyclopedia

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

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

literature

Individual evidence

  1. ^ Jack Edmonds , Richard M. Karp : Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems . In: J. ACM . tape 19 , no. 2 , 1972, p. 248-264 , doi : 10.1145 / 321694.321699 .
  2. Santanu Saha Ray: Graph Theory with Algorithms and its Applications . 1st edition. Springer India, New Delhi, et al. 2013, ISBN 978-81-322-0749-8 , pp. 167-175 .