18.04.2026Oben sehen sie ein Netzwerk aus Rohren und Verbindungen durch die eine Substanz fließen kann, zum Beispiel Wasser. Jedes Rohr hat eine bestimmte Kapazität, es kann also nicht mehr Wasser fließen als diese maximale Menge. Die Quelle wird links gezeigt mit grünem Rand, und die Senke ganz rechts mit rotem Rand. Das Problem besteht darin, herauszufinden welcher maximale Fluß von Quelle bis Senke durch das Netzwerk fließen kann, und welche Rohre dabei zu nutzen sind.
Aus mathematischer Sicht ist dieses Wassernetz nur noch ein gewichteter Graph, mit gerichteten Kanten (Rohre) zwischen Knoten, wobei jedem Kant eine Kapazität zugewiesen ist. Die Knoten können so viel Fluß schaffen wie nötig.
Auf der obigen Abbildung sehen sie eine gültige Lösung des Flußproblems für das oben betrachtete Netzwerk, wobei der gewählte Fluß durch die blauen Linien angedeutet wird. Die allgemeine Methode zur Lösung des Problems heißt die Ford-Fulkerson Methode, insbesondere nutzen wir den Edmonds-Karp Algorithmus. Für den Rest dieser Seite untersuchen wir wie man so einen Fluß algorithmisch findet.
Eine bewiesene Eigenschaft von Netzwerkfluss-Graphen ist das es einen Minimalschnitt gibt, der die Quelle von der Senke trennt, und dessen Summe an Kapazitäten gleich dem maximalem Fluß durch das Netzwerk ist. Die Abbildung oben zeigt einen solchen Schnitt durch die gelben Linien an. Man beachte, dass die Linien das Netzwerk in zwei Häften trennt, so dass der gesamte Fluß von Quelle zu Senke durch diesen Schnitt passieren muss.
Der Edmonds-Karp Algorithmus wird auf den sogenannten Residualgraphen angewandt, der oben für dasselbe Netzwerk wie zuvor angezeigt wird. Für jede Kante im ursprünglichen Netzwerk gibt es im Residualgraphen zwei Kanten: eine Vorwärtskante (dunkelgrau) in derselben Richtung wie das Original, und eine Rückwärtskante (hellgrau) in entgegengesetzer Richtung. Die Vorwärtskante berücksichtigt wieviel mehr Fluß vorwärts eingerichtet werden kann, wohingegen die Rückwärtskante berücksichtigt wieviel Fluß schon festgelegt ist und wieder entfernt werden kann. Jeder Erweiterungspfad den der Algorithmus findet ist ein Pfad von Quelle zu Senke durch diesen Residualgraphen. Beachten sie, dass die Kanten im Residualgraph gewichtet sind, dies aber in der Abbildung einfachheitshalber weggelassen wurde. Wenn eine Kante fehlt ist die Gewichtung gleich null.
Die obige Animation lässt Edmonds-Karp auf unserem Netzwerk laufen. Drücken Sie Play, um einen Durchlauf zu starten: eine Breitensuche (siehe Graphensuche) erkundet den Residualgraphen von der Quelle zur Senke und färbt durchlaufene Kanten dunkelgrün ein. Sobald die Senke erreicht ist, blinkt der gefundene kürzeste augmentierende Pfad violett auf. Der Algorithmus schiebt dann so viel Fluss entlang dieses Pfades, wie sein Engpass erlaubt, und der Residualgraph wird neu angepasst — gesättigte Vorwärtskanten verschwinden und neue Rückwärtskanten öffnen sich dort, wo Fluss geschoben wurde. Das Verfahren wiederholt sich, bis kein Pfad von der Quelle zur Senke mehr im Residualgraphen existiert: dann entspricht der gesamte geschobene Fluss dem maximalen Fluss des Netzwerks.
Hier sehen wir wieder eine Sicht auf den Edmonds-Karp Algorithmus, wo die kürzesten Pfade die grundlegende Einheit sind und in hellblau gezeigt werden. Wir sehen dann ob die Kanten dieser Pfade zum Fluß addiert werden (grün) oder vom Fluß abgezogen werden (rot). Nach und nach baut sich der gesamte Netzwerkfluss (dunkelblau) auf. Man beachte das mit kürzestem Pfad die Anzahl der Knoten gemeint sind.
Die Claude Opus LLM half bei der Gestaltung dieser Seiten. Es gibt mehr zu Algorithmen und Datenstrukturen auf unserer Hauptseite zu entdecken.
Bitte teilt diese Seite auf Social Media!