Dinic Algorithmus

[Gast]

Also der Dinic Algorithmus ist ja eine Abwandlung vom Ford-Fulkerson Algorithmus, diesen habe ich mittlwereile auch verstanden : Solange es einen möglichen Weg mit freier Kapazität von Quelle nach Senke gibt, wird dieser benutzt und auch die "Rückkanten" eingezeichnet.

so weit, so schwer.

Worin besteht aber nun die Verbesserung des dinic algorithmus , man findet immer nur dass er schneller läuft, aber ned warum....?

Es handelt sich übrigens bei beiden algorithmen um Algorithmen, die das Maximum flow Problem : http://en.wikipedia.org/wiki/Maximum_flow_problem
behandeln....

[Trap]

Edmonds-Karp ist ursprünglich O(V*E²), Dinic ist O(V²*E). Das liegt einfach daran, dass in der ursprünglichen Version von Edmonds-Karp die kürzesten Wege ineffizient gesucht wurden.

Ford-Fulkerson nimmt irgendeinen Pfad, das ist in pathologischen Fällen extrem lahm, wenn man immer den kürzesten Pfad nimmt (Edmonds-Karp in Wikipedia) ist es schon ziemlich gut.

In der Wikipedia-Liste fehlt übrigens highest-label preflow-push was im Moment meines Wissens nach der effizienteste Algorithmus ist.

[Gast]

Edmonds-Karp ist ursprünglich O(V*E²), Dinic ist O(V²*E). Das liegt einfach daran, dass in der ursprünglichen Version von Edmonds-Karp die kürzesten Wege ineffizient gesucht wurden.

Ok, aber wie werden die kürzesten Wege in Dinic anders gesucht ?

Bei der Konstruktion eines Erweiterungsweges für ein Netzwerk mit Fluss f ist zu beobachten, dass
viele der betrachteten Kanten nicht in Frage kommen. Dies ist Ausgangspunkt für den Algorithmus von
Dinic. Es wird in jedem Durchgang ein Hilfsnetzwerk erzeugt und in diesem ein Fluss bestimmt.
Mit diesem wird dann der Fluss auf dem eigentlichen Netzwerk erhöht. Das Hilfsnetzwerk entsteht aus
G_f, indem dort „überflüssige“ Kanten und Ecken entfernt werden. Auf dem Hilfsnetzwerk wird ein
Fluss konstruiert, der zwar nicht maximal sein muss, für den es aber keinen Erweiterungsweg gibt, der
nur aus Vorwärtskanten besteht. Ein solcher Fluss wird blockierender Fluss genannt.
Somit ergeben sich drei Phasen für den Algorithmus von Dinic:
Phase 1: Konstruktion des Hilfsnetzwerkes
Phase 2: Bestimmung des blockierenden Flusses
Phase 3: Flussvergrößerung

Sprich : Es wird ein Hilfsnetzwerk erstellt, in dem nur Kanten drin sind, die auch in frage kommen , dass sie als erweiterungsweg nicht in Frage kommen.
Aber woran merkt man das manche Kanten dafür nicht in Frage kommen ?

[Trap]

Ja, die ursprüngliche Version ist mit Hilfsnetzwerken. Das zu erklären braucht aber zuviel Text, eine einfachere Version die aquivalent dazu ist:
An alle Knoten i eine Entfernung zur Senke d(i) annotieren (BFS von der Senke aus), beim Wege vorwärts suchen nur Kanten (i,j) betrachten mit d(i)=d(j)+1, Knoten bei denen alle ausgehenden Kanten dieser Art 0 verbleibende Kapazität haben als blockiert markieren und beim Vorwärtssuchen ignorieren. Wenn die Quelle blockiert ist von vorne anfangen.

[Gast]

thx!