Dlaczego złożoność ujemnego anulowania cyklu ?

9

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ą:VAUW

  • Maksymalne koszty na początku nie mogą przekraczaćAUW
  • 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źć wO(VA)

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.O(V2AUW)AUWAUWVAO(A2VUW)

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?

rumtscho
źródło

Odpowiedzi:

-1

Według TopCodera poprawny czas działania to .O(A2VUW)

użytkownik9099
źródło
7
Przyjemne byłoby małe wyjaśnienie.
jmite