Seite 1 von 1

EdmondsKarp == Dinic?

Verfasst: 28. Feb 2015 18:09
von hanneswernery
Hey

ich habe etwas Diskussionsbedarf was den Unterschied zwischen EK und Dinic bei der Implementierung angeht. Denn mir ist momentan nicht ganz bewusst, worin sich die beiden Algorithmen unterscheiden - was ja nur bedeuten kann, dass ich einen der beiden nicht richtig verstanden haben.

Bei EK starte ich doch eine Breitensuche (im Residualgraphen) von S und sobald ich T gefunden habe, erhöhe ich den Fluss auf diesem Pfad nach T maximal. Solange bis ich keinen Pfad mehr bilden kann (T nicht mehr finde).

Wenn ich mir gerade Dinic durchlese, wende ich doch zunächst auch wieder Breitensuche (im Residualgraphen) an und suche dann einen "blocking flow" (Ausschöpfen einer Kante auf dem Pfad). Wiederhole solange, bis ich keinen Pfad mehr nach T finde.

Mir ist nicht klar, worin sich Dinic unterscheidet, da ich ja auch bereits in EK Breitesnsuche anwende und einen maximalen Fluss (= "blocking flow") auf diesem Pfad lege. Was übersehe ich hier?

Mfg

Re: EdmondsKarp == Dinic?

Verfasst: 3. Mär 2015 20:05
von hanneswernery
Wie sich beim Gespräch herausstellte, habe ich Dinic sehr missverstanden. Habe ihn nun neu implementiert. Er unterscheidet sich sehr von EK und läuft effizienter ;)

Re: EdmondsKarp == Dinic?

Verfasst: 18. Mär 2015 10:29
von Prof. Karsten Weihe
Ich möchte noch einmal den Unterschied kurz und präzise zusammenfassen:

Edmonds-Karp berechnet und behandelt einen kürzesten augmentierenden Pfad nach dem anderen. Dinic berechnet alle kürzesten Pfade - genauer: die Vereinigung aller kürzesten Pfade - und behandelt sie auch alle zusammen.

Saturierung eines augmentierenden Pfades bei Edmonds-Karp verallgemeinert sich zu Berechnung eines blockierenden Flusses in der Vereinigung der kürzesten Pfade (wenn die Vereinigung nur einen Pfad enthält, sind blockierende Flüsse genau saturierende Augmentierungen auf diesem Pfad).

Der Witz an Dinic' Vorgehen ist, dass die Vereinigung aller kürzesten Pfade asymptotisch schneller blockiert werden kann, als wenn jeder Pfad wie bei Edmonds-Karp einzeln blockiert werden müsste.

KW