A maximum flow Der Cycle Cancelling Algorithmus Technische Universität München
ahuja

Der kostenminimale Fluss nutzt nicht die teure Kante mit Kosten 3.

Das Min-Cost Flow Problem

Die Planung von Straßennetzen, Pipelines or Datennetzwerken sind die Motivation für die Flussprobleme genannte Klasse von Optimierungsproblem. Der charakterisierende Aspekt der zu planenden Netzwerke ist, dass eine Art Ressource durch die Kanten eines Netzwerks transportiert werden muss, welche jedoch nur eine bestimmte Menge an Fluss zulassen. Für manche der Optimierungsprobleme haben diese Transportkanten noch weitere Eigenschaften, welche es zum Beispiel motivieren, den Kanten Kosten zuzuweisen - beispielsweise Mautgebühren für die Nutzung von Straßen.

In solch einer Problemstellung ist es interessant, wie ein bestimmter Fluss mit minimalen Kosten durch das Netzwerk geschickt werden kann. Diese Problem wird das Min-Cost Flow Problem genannt.

Dieses Applet präsentiert den Cycle-Cancelling Algorithmus, welcher in einem gegebenen Netzwerk einen kostenminimalen Fluss berechnet.

Was möchtest du zuerst tun?


Legende

node Knoten
edge Kante mit Kapazität 10 und Kosten 1

Legende

Auf welchem Graph soll der Algorithmus ausgeführt werden?

Nimm ein fertiges Beispiel:

Ändere den Graphen nach deinen Vorstellungen:

  • Um einen Knoten zu erstellen, mache einen Doppelklick in das Zeichenfeld.
  • Um eine Kante zu erstellen, klicke zunächst auf den Ausgangsknoten und dann auf den Zielknoten.
  • Das Kantengewicht kann mit einem Doppelklick auf die Kante verändert werden.
  • Ein Rechtsklick löscht Kanten und Knoten.

Lade den veränderten Graphen herunter:

Download

Lade einen existierenden Graphen hoch:

Ein

trat auf beim Lesen der Datei:

Fehlerbeschreibung:

                        

Was nun?

SVG Download

Legende

node Knoten
node S/T Knoten
edge Kante mit Fluss 7, Kapazität 10 und Kosten 1
edge Kante im Residualnetzwerk, Kosten 1
edge Kante auf negativem Kreis, Kosten 1

Legende

Algorithm status

Wähle zuerst einen Quellknoten aus

Klicken Sie bitte auf einen Knoten in dem Netzwerk, um ihn als Quelle/Startknoten s auszuwählen. Der Fluss geht von diesem Knoten aus. Dieser Knoten hat keinen reinfließenden Fluss und den rausfließenden Fluss ist gleich der Flussstärke.

Wähle nun eine Senke aus

Klicken Sie bitte auf einen Knoten in dem Netzwerk, um ihn als Senke/Zielknoten t auszuwählen. Der Fluss endet in diesem Knoten. Der reinfließende Fluss dieses Knotens ist gleich die Flussstärke und es gibt keinen rausfließenden Fluss.

Der Cycle Cancelling Algorithmus

Der Algorithmus kann nun starten. Klicken Sie bitte auf Nächster Schritt, um ihn zu starten.

Initialisiere den Fluss

Der Algorithmus berechnet den maximalen Fluss mithilfe von Edmonds-Karp-Algorithmus, der eine Implementierung der Ford-Fulkerson-Methode ist, ohne die Kantenkosten zu berücksichtigen.

Der Algorithmus funktioniert wie folgt:

Solange es im Residualnetzwerk einen Weg von dem Quellknoten s zur Senke t gibt, mit Kapazität > 0 auf allen Kanten im Weg, sendet der Algorithmus so viel Flusseinheiten über dem kürzesten Weg, bis die Kante mit der kleinsten Kapazität saturiert wird. Der kürzeste Weg wird mithilfe von Breitensuche gefunden. Der Algorithmus wiederholt diese Schritte, bis es keinen Augmentationspfad (Pfad mit positiver Kapazität) von s zu t mehr gibt.

Detailierter Beschreibung der Ford-Fulkerson-Methode und Initialisierung von maximalen Flüssen ist hier zu finden.

Beginne die Hauptschleife

Wenn der Algorithmus den maximalen Fluss f ( s , t ) gefunden hat, erstellt er der Residualgraph G f zu diesem Fluss wie folgt:

Jede Kante ( v , w ) G wird durch zwei neue Kanten ( v , w ) und ( w , v ) ersetzt.

Die Kante ( v , w ) hat Kosten c ( v , w ) und Restkapazität r ( v , w ) = u ( v , w ) f ( v , w ) > 0 ,wobei u ( v , w ) ist die Kapazität der Kante und f ( v , w ) der Fluss durch die Kante.

Die zweite (Rückwärts-)Kante ( w , v ) hat Kosten c ( w , v ) = c ( v , w ) und Restkapazität r ( w , v ) = f ( v , w ) > 0 .

Die Hauptschleife sucht in jeder Iteration nach negativen Kreisen (d.h. nach Kreisen, deren Gesamtgewicht negativ ist) im Residualgraph.

Falls kein negativer Kreis gefunden wird, terminiert der Algorithmus.

Mehr über Residualgraphen lesen oder üben:

Suche einen negativen Kreis

Man findet in dem Residualgraph negativen Kreisen, indem man den Bellman-Ford-Algorithmus wie folgt ausführt:

Wenn N die Anzahl der Knoten in dem Graph ist, wird der Algorithmus zuerst N 1 mal ausgeführt und sollte den kürzesten Weg von s nach t gefunden haben. Dann wird der Algorithmus noch einmal ausgeführt und wenn der kürzeste Weg, der in der N 1 -ten Ausführung gefunden wurde, sich nicht verändert hat, gibt es keinen negativen Kreis. Andernfalls nimmt der Algorithmus einen Knoten, dessen Abstand sich geändert hat, und geht von ihm über seine Vorgänger, bis einen Kreis W gefunden wird. W ist der gesuchte negative Kreis.

Weitere Informationen zum Bellman-Ford-Algorithmus findet man hier.

Eliminiere Kreis

Wenn der Algorithmus einen negativen Kreis findet, augmentiert er δ := m i n { r ( v , w ) : ( v , w ) W } Floweinheiten durch den Kreis W , um die Kante mit minimalen Restkapazität zu saturieren (d.h. mit Fluss ausfüllen), sodass der negative Kreis W aus dem Residualgraph entfernt wird.

Dann geht der Algorithmus zurück zur Hauptschleife, um den Residualgraph für andere negative Kreise zu überprüfen.

Fertig

Der Algorithmus terminiert mit maximalem Fluss von:

-

und minimalen Kosten für diesen Fluss:

-

Der Residualgraph enthält keine negativen Kreise, daher wird ein Min-Cost-Flow gefunden.

Was nun?

Forschungsaufgaben ausprobieren?

s ← wähle(v)

t ← wähle(v)

BEGIN

|

| (* Initialisiere max. Fluss *)

| BERECHNE MAX FLOW f ( s , t ) IM NETZWERK

| MIT FORD-FULKERSON-ALGORITHMUS

|

| (* Hauptschleife *)

| WHILE (dem Residualnetzwerk G f einen

| | negativen Kreis besitzt) DO

| |

| | FÜHRE BELLMAN-FORD-ALGORITHMUS AUS

| | UM NEGATIVE KREISE W ZU

| | IDENTIFIZIEREN;

| | IF (negativer Kreis gefunden)THEN

| | | IDENTIFIZIERE Kreiskanten

| | | ( v , w ) W

| | | δ := m i n { r ( v , w ) : ( v , w ) W }

| | ENDIF

| | FOR ( ( v , w ) W )

| | | f ( v , w ) = f ( v , w ) + δ

| | ENDFOR

| |

| ENDWHILE

|

END

Variablen

Kreis Anpassung
- -

Beim Wechsel des Tabs wird der Algorithmus abgebrochen.

Du kannst die Anwendung in einem anderen Browserfenster öffnen, um parallel einen anderen Tab zu lesen.

SVG Download

Legende

node Node
nodes Source node
nodet Target node
edge Edge in residual graph, cost 1
edge Edge on negative cycle, cost 1

Legende

Choose a graph and try to answer the questions while running the algorithm!

Answer the questions while running the algorithm!


s ← pick(v)

t ← pick(v)

BEGIN

|

| (* Initialize max flow *)

| CALCULATE MAX FLOW f ( s , t ) IN THE NETWORK

| USING THE FORD-FULKERSON ALGORITHM

|

| (* Main Loop *)

| WHILE (the residual network Gf

| | contans a negative cycle) DO

| |

| | EXECUTE BELLMAN-FORD ALGORITHM TO

| | IDENTIFY A NEGATIVE CYCLE W;

| | IF (negative cycle exists)THEN

| | | IDENTIFY cycle-edges ( v , w ) W

| | | δ := m i n { r ( v , w ) : ( v , w ) W }

| | ENDIF

| | FOR ( ( v , w ) W

| | | f ( v , w ) = f ( v , w ) + δ

| | ENDFOR

| |

| ENDWHILE

|

END

In this part you can test your knowledge: What would the algorithm do?

The algorithm will be executed normally, but will stop in a few places. Then you will have to predict, what the algorithm would do next.

Hint: Recall the description of the algorithm.

If you switch tabs, the execution will be terminated.

You can open another browser window to read the description in parallel.

SVG Download

Legende

node Knoten
node S/T Knoten
edge Kante mit Kapazität 10 und Fluss 7.
edge Kante im Residualgraphen.
edge Kante auf augmentierendem Pfad.

Legende

Build the corresponding residual netwprk!

In the following exercise you will get different networks \(N\) with the respective capacities, flow values and costs \(u(e)\), \(f(e)\) and \(c(e)\) for all edges \(e \in E\), based on a current flow \(f\).

Your task is to fill the missing residual capacities \(r(e')\) bzw. \(r(e'')\) of the out- and ingoing edges \(e'\) und \(e''\) in the corresponding residual network N f .


Choose a number of networks for the exercise:


In this part you can practice the construction of residual networks!

You will get a network with current flow. Your task is to fill out the missing residual capacities and costs in the residual network!

Tip: Before you start read the information on residual networks again.

WARNING!

You can set the missing residual capacities and costs only once. When a value is set it can not be changed any more.

Good Luck!

If you switch tabs, the execution will be terminated.

You can open another browser window to read another tab in parallel.