Chcemy rozwiązać problem minimalnego przepływu kosztów za pomocą ogólnego algorytmu anulowania cyklu ujemnego. Oznacza to, że zaczynamy od losowego prawidłowego przepływu, a następnie nie wybieramy żadnych „dobrych” cykli ujemnych, takich jak cykle o średnich kosztach minimalnych, ale używamy Bellman-Ford do odkrycia minimalnego cyklu i zwiększenia wzdłuż odkrytego cyklu. Niech będzie liczbą węzłów na wykresie, liczbą krawędzi, maksymalną pojemnością krawędzi na wykresie, a maksymalnymi kosztami krawędzi na wykresie. Następnie moje materiały do nauki twierdzą:
- Maksymalne koszty na początku nie mogą przekraczać
- Powiększenie w jednym cyklu ujemnym zmniejsza koszty o co najmniej jedną jednostkę
- Dolna granica kosztów minimalnych wynosi 0, ponieważ nie zezwalamy na koszty ujemne
- Każdy cykl ujemny można znaleźć w
Z tego wynika, że złożoność algorytmu wynosi . Rozumiem logikę każdego z tych twierdzeń, ale uważam, że złożoność jest inna. W szczególności, maksymalna liczba augmentacji jest podana przez jedną jednostkę przepływu na augmentację, koszty z do zera, dając nam maksimum augmentacji . Musimy odkryć cykl ujemny dla każdego, więc mnożymy maksymalną liczbę augmentacji przez czas potrzebny do wykrycia cyklu ( ) i do dla algorytmu.
Czy może to być błąd w materiałach do nauki (jest to tekst dostarczony przez profesora, a nie notatki studenta z kursu), czy też moja logika jest błędna?