Ahuja-Orlin fehlende Break Condition

Moderator: Effiziente Graphenalgorithmen

rocky07
Neuling
Neuling
Beiträge: 1
Registriert: 20. Jul 2015 07:56

Ahuja-Orlin fehlende Break Condition

Beitrag von rocky07 » 3. Aug 2018 10:22

Hallo zusammen,

ich habe da ein Problem beim Algo von Ahuja-Orlin festgestellt und komme nicht weiter. Und zwar ist die einzige Break Condition das d(s) = n ist.

In den meisten Fällen klappt alles gut, außer wenn ich einen Graphen habe der nach dem letzten augmentieren alle ausgehenden Kanten vom Source Node im Residualgraphen entfernt. Heißt also wenn alle ausgehenden Kanten vom Source Node maximal ausgeschöpft sind. In dem Fall kann ich mit dem Algorithmus die distance labels nicht mehr hochzählen weil ich ja dann keine ausgehenden Kanten vom Source Node habe die admissible sind. So kann ich also die einzige Break Condition nicht erreichen und lande im Algo unter 3.2.1 (distance label erhöhen) eigentlich in einen Error weil ich das Minimum von nichts setzen würde.

Ich habe auch im Buch Network Flow von Ahuja, Magnanti und Orlin nachgeschaut, da ist genau das gleiche Problem und in allen Beweisen kein einziges Wort für diesen einen Fall. Habe ich ein wichtiges Detail übersehen? Kann ich einfach die Break Condition ergänzen das der Algo endet wenn der Source Node maximal ausgeschöpft ist?


Vielen Dank schon mal!

Link zu Ahuja-Orlin:
https://wiki.algo.informatik.tu-darmsta ... huja-Orlin

Zurück zu „Effiziente Graphenalgorithmen“