Metraipolis › archive › dc_56a0a0dd35bb

Algorithmus von Edmonds und Karp — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/Algorithmus_von_Edmonds_und_Karp
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-07T18:21:25.240Z
SHA-256 of the archived text
6f8239c0dfb4c1c7ca4a7fe007ed9c886de80b41f92fe025f522b0ec4a3a2a42
Stable URL of this page
https://metraipolis.com/documento/dc_56a0a0dd35bb

How to cite

Algorithmus von Edmonds und Karp — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Algorithmus_von_Edmonds_und_Karp (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_56a0a0dd35bb (Metraipolis archive dc_56a0a0dd35bb, sha256 6f8239c0dfb4c1c7ca4a7fe007ed9c886de80b41f92fe025f522b0ec4a3a2a42)
BibTeX
@misc{dc56a0a0dd35bb,
  title = {Algorithmus von Edmonds und Karp — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Algorithmus_von_Edmonds_und_Karp},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_56a0a0dd35bb; sha256 6f8239c0dfb4c1c7ca4a7fe007ed9c886de80b41f92fe025f522b0ec4a3a2a42},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Algorithmus_von_Edmonds_und_Karp. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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. In den meisten Implementierungen wird der kürzeste Pfad durch eine Breitensuche ermittelt, was zu einer Laufzeit in 𝒪(|V|⋅|E|2) führt. 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 𝒪(|V|2⋅|E|).

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «Graphentheorie»).
Fonte: Wikipedia in tedesco, voce «Algorithmus von Edmonds und Karp» — https://de.wikipedia.org/wiki/Algorithmus_von_Edmonds_und_Karp
Wikidata Q1302658: «algorithm» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1302658
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Algorithmus_von_Edmonds_und_Karp?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 220158776, consultata il 2026-11-07T18:14:43.147Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: f83536404767e0d8eb6e455d71f88e85a0cdeabdb5d0ab660da6284c8810a79b