Algorithmus von Dinic

Moderator: Effiziente Graphenalgorithmen

Siggi
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 101
Registriert: 15. Okt 2006 12:46

Algorithmus von Dinic

Beitrag von Siggi »

Hallo,

ich versteh den Algorithmus von Dinic nicht ganz, wäre nett, wenn mir da jemand helfen könnte.
Wofür braucht der Algorithmus einen layerd Graph? Und kann mit bitte jemand ein Netz zeichnen, das einen blockierenden fluss hat, der aber nicht maximal ist. Ich kann mir das grade irgendwie nicht vorstellen. Wenn jeder Pfad von s zu t eine saturierenden Kante enthält, und ich keine Rückwärtskanten einfüge, wie kann ich dann noch einen augmentierenden Pfad finde?!?

[edit]
O.K. Die Frage mit dem layerd Graph hat sich erledigt. Ich habe die Definition davon falsch verstanden.
Aber nur um noch mal sicher zu gehen, der layerd Graph enthält nicht alle Kanten des ursprünglichen Graphen? Also falls eine Kante zwei Knoten mit gleicher Distanz verbindet, so ist sie im layerd Graph nicht enthalten. Nach der Phase von Dinic kann es dann aber sein, dass eine Kante saturiert ist, und damit wegfällt. Dann berechne ich meine Distanzen neu und dann könnte die Kante in den layerd Graph aufgenommen werden, die ich vorher nicht nehmen konnte. Stimmt das so in etwa?
[/edit]

Benutzeravatar
Arki
Mausschubser
Mausschubser
Beiträge: 62
Registriert: 15. Sep 2004 00:47
Wohnort: Darmstadt
Kontaktdaten:

Re: Algorithmus von Dinic

Beitrag von Arki »

Ja, ich denke so in etwa sollte das hinkommen. Ich versuche mal zu beschreiben, wie ich es verstanden habe.

Der Layered Graph pro Phase besteht lediglich aus admissible arcs (in Anbetracht des aktuellen Rediualgraphen!). Das heißt ferner, wir finden dort nur s-t-Pfade, die kantenkürzest sind. Wir bauen nun pro Phase einen Blocking Flow auf. Der Blocking Flow setzt sich aus mehreren Flüssen auf s-t-Pfaden zusammen und muss nicht zwangsweise maximal sein (siehe unten die Beispielinstanz). Aber wir saturieren auf jedem dieser Pfade mindestens eine Kante (eben die Kante mit minimaler Restkapazität). Es ist egal welchen Pfad man wählt, man findet logischerweise immer eine solche blockierende Kante.

Für die nachfolgenden Phasen heißt dies:
Diese kantenkürzesten s-t-Pfade werden immer länger, daher denke ich, dass du nun auch Kanten im Layered Graph haben kannst, die du in einer vorhergehenden Iteration nicht betrachtet hast (da ein Knoten, der beispielsweise vorher in BFS-Layer 3 war, nun auf BFS-Layer 4 sein kann). Diese s-t-Pfade können aber nicht mehr als n-1 Kanten haben, also sollte der Algorithmus nach maximal n-2 Phasen terminieren (dann haben wir alle Pfade gefunden, auf denen Fluss fließen kann, die nicht mehr als n-1 Kanten haben, wobei mindestens eine dieser n-1 Kanten eine blockierende Kante ist.

Beispielinstanz:
V = {1, 2, 3, 4, 5, 6}
A = {(1,2,3), (1,3,5), (2,4,3), (2,5,3), (3,4,3), (3,5,1), (4,6,4), (5,6,5)}
Die Kantentripel sind so zu lesen: (Startknoten, Endknoten, Kapazität)

Grüße,
Markus
Der Biber machts richtig: Nagt alles kaputt!

Siggi
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 101
Registriert: 15. Okt 2006 12:46

Re: Algorithmus von Dinic

Beitrag von Siggi »

Vielen Dank, für die gute Erklärung. Ich denke mal, damit sollte das Problem auch gelöst sein.
Das Beispiel ist ein bisschen komisch, bzw. am Anfang war der Fluss blockierend und maximal. Also wenn ich die Flüsse folgendermaßen aufbaue:
3 Einheiten über 1,2,5,6 (damit ist auch der Pfad 1,2,5,6 blockiert), eine Einheit über 1,3,4,6 womit die Kante 3,5 saturiert ist und dann noch drei Einheit über 1,3,4,6. Der Fluss sollte ja maximal sein. Es gibt aber auch noch mehr möglichkeiten, die Pfade zu suchen, damit der Fluss blockierend ist, aber nicht maximal (zum Beispiel drein Einheiten über 1,2,4,6).

Gruß Christian

Benutzeravatar
Arki
Mausschubser
Mausschubser
Beiträge: 62
Registriert: 15. Sep 2004 00:47
Wohnort: Darmstadt
Kontaktdaten:

Re: Algorithmus von Dinic

Beitrag von Arki »

Ja gut, du kannst die Pfade natürlich auch anders aufbauen :). Ich hatte es zuerst so (in dieser Reihenfolge):

1-3-5-6, saturiert 3-5 (+Fluss 1)
1-2-4-6, saturiert 1-2, 2-4 (+Fluss 3)
1-3-4-6, saturiert 4-6 (+Fluss 1)

Dabei sieht man auch gut, dass auch nicht saturierte Kanten aus dem Layered Graph quasi "entfernt" werden, da sie ja nicht mehr von s aus erreichbar sind. Jedenfalls hat man an dieser Stelle nen Blocking Flow gefunden und geht in die zweite Phase über. Der Residualgraph zeigt dann auch, dass die Knoten in andere BFS Levels rutschen und die kantenkürzesten Pfade dadurch länger werden.

Grüße,
Markus
Der Biber machts richtig: Nagt alles kaputt!

Commander
Neuling
Neuling
Beiträge: 10
Registriert: 11. Mai 2005 17:37

Re: Algorithmus von Dinic

Beitrag von Commander »

Arki hat geschrieben:Ja gut, du kannst die Pfade natürlich auch anders aufbauen :). Ich hatte es zuerst so (in dieser Reihenfolge):

1-3-5-6, saturiert 3-5 (+Fluss 1)
1-2-4-6, saturiert 1-2, 2-4 (+Fluss 3)
1-3-4-6, saturiert 4-6 (+Fluss 1)

Dabei sieht man auch gut, dass auch nicht saturierte Kanten aus dem Layered Graph quasi "entfernt" werden, da sie ja nicht mehr von s aus erreichbar sind.
soweit klar...
Arki hat geschrieben: Jedenfalls hat man an dieser Stelle nen Blocking Flow gefunden und geht in die zweite Phase über. Der Residualgraph zeigt dann auch, dass die Knoten in andere BFS Levels rutschen und die kantenkürzesten Pfade dadurch länger werden.
Das kann ich nicht nachvollziehen - was ist denn die zweite Phase? Eigentlich doch wieder einen layered Graoh bilden oder - aber warum sollen die Knoten dann in andere Level rutschen?

Benutzeravatar
Arki
Mausschubser
Mausschubser
Beiträge: 62
Registriert: 15. Sep 2004 00:47
Wohnort: Darmstadt
Kontaktdaten:

Re: Algorithmus von Dinic

Beitrag von Arki »

Angenommen du hast in der ersten Phase einen Layered Graph mit d(s) = 3. Dann findest du in dieser Phase blockierende Kanten für alle kantenkürzesten s-t-Wege der Länge 3. Dadurch, dass du einen Blocking Flow aufbaust, gibts keine weiteren Wege der Länge 3 mehr, auf denen du Fluss schicken würdest. Daher wird d(s) > 3 für die folgenden Layered Graphs. Die s-t-Wege können nur länger werden, nicht kürzer, weil du evtl. Fluss über eine Rückwärtskante zurückrouten musst (dazu müssen Knoten in andere Layer rutschen), um eine evtl. falsch getroffene Entscheidung in einer früheren Iteration zu korrigieren. Jetzt klar?
Der Biber machts richtig: Nagt alles kaputt!

marluwie
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 18. Okt 2005 22:33

Re: Algorithmus von Dinic

Beitrag von marluwie »

Der Satz "But in contrast to other variants it does not add reverse arcs after an augmentation" auf Folie 183 verwirrt mich aber ein wenig. Denn ohne Rückwärtskanten im Residualgraph, kann man in der zweiten Iteration keinen Layered Graph aufstellen. Die Kante (4, 2) im Residualgraph fehlt. Man kommt nur auf einen Fluss von 5. Aber optimal ist 7.
Oder heißt der Satz nur, dass während der Blockierenden-Fluss-Berechnung keine Rückwärtskanten benötigt werden und man das dann in einem Rutsch vor dem BFS macht?
"You can't change anything by fighting or resisting it. You change something by making it obsolete through superior methods." (Buckminster Fuller)

marluwie
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 18. Okt 2005 22:33

Noch eine Frage

Beitrag von marluwie »

Und gleich noch eine Frage zu nächsten Folie (184). Ist da wirklich u gemeint oder sollte es lieber r sein (wegen Residualkapazitäten). Welches Potential hat s und t? Da sie keine eingehenden bzw. ausgehenden Kanten haben müsste p(s) = p(t) = 0 sein, oder (die Summe von k = 1 bis k = 0 ist mathematisch 0. Also müsste die Summe über die leere Menge auch 0 sein)? Dann gibt es nie etwas zu pushen.
"You can't change anything by fighting or resisting it. You change something by making it obsolete through superior methods." (Buckminster Fuller)

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Re: Algorithmus von Dinic

Beitrag von yourmaninamsterdam »

marluwie hat geschrieben:Der Satz "But in contrast to other variants it does not add reverse arcs after an augmentation" auf Folie 183 verwirrt mich aber ein wenig. Denn ohne Rückwärtskanten im Residualgraph, kann man in der zweiten Iteration keinen Layered Graph aufstellen. Die Kante (4, 2) im Residualgraph fehlt. Man kommt nur auf einen Fluss von 5. Aber optimal ist 7.
Oder heißt der Satz nur, dass während der Blockierenden-Fluss-Berechnung keine Rückwärtskanten benötigt werden und man das dann in einem Rutsch vor dem BFS macht?
Das ist so zu verstehen:
Du hast im Rahmen der Berechnung des Layered Graphs ggf. Kanten (und Knoten) weggelassen (1), da der Layered Graph nur kürzeste s-t-Pfade enthält.
Bei der Bestimmung des blockierenden Flusses entfernst du Kapazitäten wie üblich, setzt aber an Stelle der entfernten Kapazitäten (und im Falle von x_ij =u_ij ganzer Kanten) keine Rückwärtskanten ein. Danach nimmst du die bei (1) entfernten Knoten und Kanten wieder ein und bestimmst den nächsten Layered Graph für die kommende Iteration.

marluwie
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 18. Okt 2005 22:33

Re: Algorithmus von Dinic

Beitrag von marluwie »

yourmaninamsterdam hat geschrieben:Danach nimmst du die bei (1) entfernten Knoten und Kanten wieder ein und bestimmst den nächsten Layered Graph für die kommende Iteration.
Genau. Aber das ändert dann im Beispiel von oben auch nichts mehr. Denn der Graph ist hier bereits ein Layered Graph. In der ersten Iteration wird durch den blockierenden Fluss ein Schnitt gefunden, der eine erneute BFS überflüssig macht. s kann von t nicht mehr erreicht werden. Um aber einen minimalen Schnitt zu finden, braucht man im Residualgraph die Rückwärtskante (4, 2).
"You can't change anything by fighting or resisting it. You change something by making it obsolete through superior methods." (Buckminster Fuller)

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Re: Algorithmus von Dinic

Beitrag von yourmaninamsterdam »

Ich muss hier zugeben, dass ich mir das Beispiel nicht angesehen habe. Ich schaue mir das genauer an, wenn ich mich beim Lernen thematisch wieder in ähnlichen Gebieten bewege.
Vielleicht hat ja vorher jemand anders ne Lösung parat.

Benutzeravatar
blowfish
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 241
Registriert: 18. Okt 2006 16:00

Re: Algorithmus von Dinic

Beitrag von blowfish »

wenn ich das richtig verstehe, sind layered graphs im bezug auf residualgraphen definiert. um also den neuen layered graph zu berechnen, musst du erst den neuen residualgraph bestimmen. da kommt dann auch die rückwärtskante ins spiel, die du gesucht hast (vermute ich, hab mir das beispiel jetzt nicht angeschaut). du fügst die rückwärtskanten halt nicht nach jeder augmentierung ein, sondern erst, wenn du einen blocking flow gefunden hast.
Ein Hemd ist Einstellungssache!

Siggi
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 101
Registriert: 15. Okt 2006 12:46

Re: Algorithmus von Dinic

Beitrag von Siggi »

Also ich verstehe das so, dass wir auf unserem Layered Graph (der ja nicht alle Kanten enthalten muss) einen blockierenden Fluss finden. Es werden aber nirgendwo die Rückkanten eingefügt. Im normalen Graph wird nun dieser Fluss eingetragen. Da der Fluss ja blockierend war, gibt es dort jetzt Kanten mit Residualkapazität von 0. Diese Kanten können entfernt werden. Da der Fluss ja über den Layered Grapgh geht, also damit über den kürzesten Weg, wird so eine Kante aus dem kürzesten Weg gelöscht. Damit erhalten die Knoten auch teilweise andere Distanzen, was einen neuen Layered Graph zur folge hat, der jetzt unter Umständen andere Kanten enthält, die bei dem vorherigen Graph nicht enthalten waren.

In verschiedenen Beispielen funktioniert das auch ohne Rückkante, nur in dem Beispiel von oben nicht. Gibt es evtl. eine Bedingung für die Graphen, die nicht beachtet werden? Wie ist das, wenn wir nach einem blockierenden Fluss in den richtigen Graphen (also nicht den Layered Graph) die Rückwärtskanten einfügen? Können wir dann den Fluss in n-1 Schleifen finden?

Gruß Christian

Antworten

Zurück zu „Effiziente Graphenalgorithmen“