Algorithmus von Edmonds und Karp

Dieser Artikel behandelt den Edmonds-Karp-Algorithmus. Er ist nicht zu verwechseln mit Edmonds' Matching Algorithmus.

Der Edmonds-Karp-Algorithmus ist in der Informatik und der Graphentheorie eine Implementierung des Ford-Fulkerson-Algorithmus zur Berechnung des maximalen s-t-Flusses in Netzwerken mit positiven reellen Kapazitäten. Sie verwendet den jeweils kürzesten augmentierenden Pfad in jedem Schritt, was sicherstellt, dass der Algorithmus in polynomieller Zeit terminiert.^[1]

In den meisten Implementierungen wird der kürzeste Pfad durch eine Breitensuche ermittelt, was zu einer Laufzeit in ${\displaystyle {\mathcal {O}}(|V|\cdot |E|^{2})}$ führt.^[2] Der Algorithmus wurde zuerst 1970 von dem russischen Wissenschaftler E. A. Dinic publiziert und später unabhängig von Jack Edmonds und Richard M. Karp, die ihn 1972 publizierten, entdeckt. Dinics Algorithmus enthält zusätzliche Techniken zur Reduzierung der Laufzeit auf ${\displaystyle {\mathcal {O}}(|V|^{2}\cdot |E|)}$.

Literatur

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001, ISBN 0-262-03293-7, Unterkapitel 26.2: The Ford-Fulkerson method, S. 651–664.
• Bernhard Korte, Jens Vygen: Kombinatorische Optimierung. Springer Berlin Heidelberg, 2012, ISBN 978-3-642-25400-0, Unterkapitel 8.3: Der Edmonds-Karp-Algorithmus, S. 195–196.