Edmonds Karp Algorithmus am Beispiel (Uni Köln)

Die Augmentierten Wege sind hier noch nicht eingetragen, bitte ergänzen und diesen Hinweis entfernen.

Einsatz des Edmonds/Karp Algorithmus zur Bestimmung des maximalen Flusses (der Algo ist eine Verbesserung des Ford/Fulkerson)
Wir suchen den maximalen Fluss im folgenden Graphen D:

1. Schritt

min {sd, de, et} = 3

2. Schritt

min {sa, ab, bc, ct} = 4

3. Schritt

min {sa, ab, bc, cd, de, et} = 2

Ergebnis

kein augmentierender Weg mehr vorhanden.