Udoskonalenie jena w stosunku do Bellmana-Forda

Question

Natknąłem się na słynną metodę optymalizacji algorytmu Bellmana-Forda, którą otrzymałem początkowo od Wikipedia, a następnie znalazłem to samo ulepszenie w kilku podręcznikach w sekcji Ćwiczenia (na przykład, jest to problem 24-1 w Cormen i Web exercise N5 w "Algorytmach" Sedgewicka).

Oto poprawa: druga poprawa

Yen pierwszy przypisuje pewną dowolnej kolejności liniowej na wszystkich wierzchołkach, a następnie dzieli zbiór wszystkich krawędziach na dwa podzbiory. Pierwszy podzbiór, Ef, zawiera wszystkie krawędzie (vi, vj) takie, że i < j; drugi, Eb, zawiera krawędzie (vi, vj) takie, że i> j. Każdy wierzchołek jest odwiedzany w kolejności v1, v2, ..., v | V |, rozluźniając każdą wychodzącą krawędź od tego wierzchołka w Ef. Każdy wierzchołek jest następnie odwiedzany w kolejności v | V |, v | V | -1, ..., v1, rozluźniając każdą wychodzącą krawędź od tego wierzchołka w Eb. Każda iteracja głównej pętli algorytmu, po pierwszej, dodaje co najmniej dwie krawędzie do zestawu krawędzi, których spokojne odległości odpowiadają poprawnym najkrótszym odległościom ścieżki: jeden od Ef i jeden od Eb. Ta modyfikacja redukuje najgorszą liczbę iteracji głównej pętli algorytmu z | V | - 1 do | V |/2.

Niestety, nie udało mi się znaleźć dowodu na to związane | V |/2, a ponadto wydaje się, że znalazłem kontrprzykład. Jestem pewien, że się mylę, ale nie widzę, gdzie dokładnie.

Counterxample to tylko wykres ścieżki z wierzchołkami oznaczonymi od 1 do n oraz początkowym wierzchołkiem 1. (Tak więc, E = {(i, i + 1)} dla i w zakresie od 1 do n-1). W takim przypadku zbiór przednich wierzchołków jest równy E (E_f = E), a zbiór tylnych wierzchołków jest tylko pustym zbiorem. Każda iteracja algorytmu dodaje tylko jedną poprawnie obliczoną odległość, więc algorytm kończy się w czasie n-1, co jest sprzeczne z proponowanym związanym n/2.

Co robię źle?

UPD: Więc błąd był bardzo głupi. Nie rozważałem iteracji przez wierzchołki, myśląc o iteracjach jako o natychmiastowej aktualizacji kosztów ścieżki. Nie usuwam tego tematu, ponieważ ktoś go upomniał, na wypadek gdyby to ulepszenie mogło być dla kogoś interesujące.

Answer 1

Jest to w rzeczywistości najlepszy przypadek, który kończy się w 2 iteracjach bez względu na liczbę wierzchołków.

Narysuj iteracje na papierze lub wpisz kod. Pierwsza iteracja znajdzie wszystkie poprawne najkrótsze ścieżki. Druga iteracja nie zmieni niczego, a algorytm się zakończy, ponieważ zbiór wierzchołków, których odległość została zmieniona, ostatnia iteracja jest pusta.

Przebieg "do przodu" przez wierzchołki, który rozluźnia zestaw krawędzi Ef, wykona całą pracę, podczas gdy bieg "do tyłu" nic nie da, ponieważ Eb jest zbiorem pustym.