Wir wollen ein Problem mit minimalem Kostenfluss mit einem generischen Algorithmus zur Unterdrückung negativer Zyklen lösen. Das heißt, wir beginnen mit einem zufälligen gültigen Fluss und wählen dann keine "guten" negativen Zyklen aus, wie z. B. minimale durchschnittliche Kostenzyklen, sondern verwenden Bellman-Ford, um einen minimalen Zyklus und eine Erweiterung entlang des entdeckten Zyklus zu ermitteln. Sei die Anzahl der Knoten im Diagramm, A die Anzahl der Kanten, U die maximale Kapazität einer Kante im Diagramm und W die maximalen Kosten einer Kante im Diagramm. Dann behaupten meine Lernmaterialien:
- Die maximalen Kosten zu Beginn dürfen nicht mehr als A U W betragen
- Die Vergrößerung entlang eines negativen Zyklus reduziert die Kosten um mindestens eine Einheit
- Die Untergrenze für die minimalen Kosten ist 0, da wir keine negativen Kosten zulassen
- Jeder negativer Zyklus kann gefunden werden in
Daraus folgt, dass die Komplexität des Algorithmus . Ich verstehe die Logik hinter jedem der Ansprüche, denke aber, dass die Komplexität unterschiedlich ist. Insbesondere wird die maximale Anzahl von Augmentationen durch eine Durchflusseinheit pro Augmentation angegeben , wodurch die Kosten von A U W auf Null steigen und wir maximal A U W Augmentationen erhalten. Wir müssen für jeden einen negativen Zyklus entdecken, also multiplizieren wir die maximale Anzahl von Augmentationen mit der Zeit, die benötigt wird, um einen Zyklus ( V A ) zu entdecken und zu O ( A 2 V U zu gelangen) für den Algorithmus.
Könnte dies ein Fehler in den Lernmaterialien sein (dies ist ein vom Professor bereitgestellter Text, keine Notizen eines Studenten aus dem Kurs), oder ist meine Logik falsch?