EdmondsKarp == Dinic?

Moderator: Effiziente Graphenalgorithmen

hanneswernery
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 30. Dez 2012 15:26

EdmondsKarp == Dinic?

Beitrag von hanneswernery » 28. Feb 2015 18:09

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

hanneswernery
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 30. Dez 2012 15:26

Re: EdmondsKarp == Dinic?

Beitrag von hanneswernery » 3. Mär 2015 20:05

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 ;)

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: EdmondsKarp == Dinic?

Beitrag von Prof. Karsten Weihe » 18. Mär 2015 10:29

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

Antworten

Zurück zu „Effiziente Graphenalgorithmen“