Algorithmus von Edmonds und Karp
aus Wikipedia, der freien Enzyklopädie
Der Edmonds-Karp Algorithmus ist in der Informatik und der Graphentheorie eine Implementierung der Ford-Fulkerson-Methode zur Berechnung des maximalen Flusses in Netzwerken. Sie verwendet den jeweils kürzesten augmentierenden Pfad in jedem Schritt, was sicherstellt, dass der Algorithmus terminiert. In den meisten Implementierungen wird der kürzeste Pfad durch eine Breitensuche ermittelt, was zu einer Laufzeit in O(V E²) führt. Der Algorithmus wurde zuerst 1970 von dem russischen Wissenschaftler E. A. Dinic publiziert und später unabhängig von Jack Edmonds and Richard M. Karp, der ihn 1972 publizierte, entdeckt. Dinics Algorithmus enthält zusätzliche Techniken zur Reduzierung der Laufzeit auf O(V²E).
[Bearbeiten] Quellen
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 26.2: The Ford-Fulkerson method, pp.651–664.
