https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Algorithmus_von_Edmonds_und_Karp 2026-05-28T10:38:03Z Versionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale Kopie MediaWiki 1.43.8 https://wiki-de.moshellshocker.dns64.de/index.php?title=Algorithmus_von_Edmonds_und_Karp&diff=621800&oldid=prev 2022-02-13T14:39:13Z

<p></p> <p><b>Neue Seite</b></p><div>{{Dieser Artikel|behandelt den Edmonds-Karp-Algorithmus. Er ist nicht zu verwechseln mit [[Edmonds&#039; Matching Algorithmus]].}}<br /> Der &#039;&#039;&#039;Edmonds-Karp-Algorithmus&#039;&#039;&#039; ist in der [[Informatik]] und der [[Graphentheorie]] eine Implementierung des [[Ford-Fulkerson-Algorithmus]] zur Berechnung des [[Maximaler Fluss|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 [[Polynomialzeit|polynomieller Zeit]] terminiert.&lt;ref&gt;{{Literatur | Autor=[[Jack Edmonds]], [[Richard M. Karp]] | Titel=Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems | Sammelwerk=J. ACM | Band=19 | Nummer=2 | Jahr=1972 | Seiten=248–264 | DOI=10.1145/321694.321699}}&lt;/ref&gt;<br /> <br /> In den meisten Implementierungen wird der kürzeste Pfad durch eine [[Breitensuche]] ermittelt, was zu einer Laufzeit in &lt;math&gt;\mathcal{O}(|V| \cdot |E|^2)&lt;/math&gt; führt.&lt;ref&gt;{{Literatur | Autor=Santanu Saha Ray | Titel=Graph Theory with Algorithms and its Applications | Auflage=1 | Verlag=Springer India | Ort=New Delhi, u. a.| Jahr=2013 | ISBN=978-81-322-0749-8 | Seiten=167–175}}&lt;/ref&gt; 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. [[Algorithmus von Dinic|Dinics Algorithmus]] enthält zusätzliche Techniken zur Reduzierung der Laufzeit auf &lt;math&gt;\mathcal{O}(|V|^2 \cdot |E|)&lt;/math&gt;.<br /> <br /> == Literatur ==<br /> * Thomas H. Cormen, [[Charles E. Leiserson]], [[Ronald L. Rivest]], Clifford Stein: &#039;&#039;Introduction to Algorithms, Second Edition&#039;&#039;. MIT Press and McGraw-Hill, 2001, ISBN 0-262-03293-7, Unterkapitel 26.2: &#039;&#039;The Ford-Fulkerson method&#039;&#039;, S. 651–664.<br /> * [[Bernhard Korte]], [[Jens Vygen]]: &#039;&#039;Kombinatorische Optimierung&#039;&#039;. Springer Berlin Heidelberg, 2012, ISBN 978-3-642-25400-0, Unterkapitel 8.3: &#039;&#039;Der Edmonds-Karp-Algorithmus&#039;&#039;, S. 195–196.<br /> <br /> == Einzelnachweise ==<br /> &lt;references /&gt;<br /> <br /> [[Kategorie:Netzwerktheorie|Edmonds und Karp]]<br /> [[Kategorie:Algorithmus|Edmonds und Karp]]<br /> [[Kategorie:Algorithmus (Graphentheorie)|Edmonds und Karp]]<br /> [[Kategorie:Optimierungsalgorithmus|Edmonds und Karp]]</div>

imported>Neutronstar2