Network Delay Time

Rozpocznij wyszukiwanie w węźle k z czasem 0 i podążaj każdym łączem, uwzględniając dotychczasowy czas. Zapisuj dla każdego węzła najkrótszy czas dotarcia, jaki udało się uzyskać. Gdy wyszukiwanie dociera do węzła nie szybciej niż odnotowany czas, zatrzymaj się: wszystko, co ta trasa mogłaby zaoferować dalej, oferowała już szybsza trasa. Gdy dociera do węzła szybciej, rekord się poprawia, a wszystko za tym węzłem również może się poprawić, więc wyszukiwanie jest kontynuowane od tego węzła.

To zawsze działa poprawnie. Wyszukiwanie zatrzymuje się tylko wtedy, gdy żadna trasa nie poprawia żadnego rekordu, a najszybsza trasa do każdego węzła w pewnym momencie poprawia jego rekord, więc każdy rekord kończy z prawdziwym najkrótszym czasem.

Problemem jest to, ile razy może poprawić się rekord węzła. Wyszukiwanie w głąb podąża pierwszym napotkanym łączem aż do końca, więc może dotrzeć do węzła wolną trasą, potem nieco szybszą, a następnie jeszcze szybszą, za każdym razem przechodząc przez wszystko za tym węzłem. Wyobraź sobie 18 bramek ustawionych w rzędzie. Między każdą parą bramek możesz wybrać bezpłatne łącze albo objazd — łańcuch łączy, których czasy sumują się do 65,536, 32,768 i tak dalej, aż do 1. Próbując najpierw objazdów, wyszukiwanie dociera do ostatniej bramki 131,072 razy, za każdym razem szybciej niż poprzednio, i za każdym razem przechodzi przez 1,700 węzłów znajdujących się za nią: około 220 milionów kroków. Dwa z dużych testów są skonstruowane w ten sposób: w jednym każdy objazd jest wymieniony przed bezpłatnym łączem, a w drugim po nim, więc wyszukiwanie potknie się na jednym z nich, niezależnie od kolejności, w jakiej próbuje łączy.

Przechowuj wstępny czas dist dla każdego węzła: 0 dla k, a nieskończoność dla pozostałych. Poluzowanie połączenia u → v o czasie w oznacza: jeśli dist[u] + w jest mniejsze niż dist[v], połączenie oferuje szybszą drogę do v, więc zmniejsz dist[v] do tej wartości. Bellman-Ford wykonuje przebiegi po całej liście i relaksuje każde połączenie w każdym przebiegu.

Dlaczego na końcu otrzymujemy poprawne czasy? Weźmy najszybszą trasę do pewnego węzła, na przykład k → a → b → v. W pierwszym przebiegu relaksowane jest k → a, gdy dist[k] wynosi już 0, więc po nim dist[a] jest ostateczne. Drugi przebieg ustala dist[b], a trzeci dist[v]. Najszybsza trasa nigdy nie musi odwiedzać węzła dwukrotnie, ponieważ pętla nigdy nie zajmuje ujemnego czasu, więc ma co najwyżej n-1 połączeń, a n-1 przebiegów ustala wartości dla każdego węzła. Przebieg, który niczego nie zmienia, dowodzi, że żaden późniejszy przebieg też niczego nie zmieni, więc możesz na nim zakończyć.

Każdy przebieg kosztuje O(E), więc w najgorszym przypadku złożoność wynosi O(n · E). Kolejność elementów na liście decyduje o tym, jak źle będzie: jeśli połączenia na jednej długiej trasie są podane od jej dalszego końca w kierunku początku, każdy przebieg ustala wartość dla jeszcze jednego węzła. Jeden duży test wygląda dokładnie tak: łańcuch z 3 000 węzłów podany w odwrotnej kolejności, co wymaga 2 999 przebiegów po 4 000 połączeń: około 12 milionów relaksacji. Przy takim rozmiarze nadal działa to wystarczająco szybko, ale nakład pracy rośnie proporcjonalnie do n razy E. Zaletą Bellmana-Forda jest coś innego: algorytm pozostaje poprawny, gdy czasy niektórych połączeń są ujemne, a Dijkstra wtedy zawodzi.

Bellman-Ford wykonuje zbędne przebiegi, ponieważ relaksuje połączenia wychodzące z węzłów, których czasy nie są jeszcze ostateczne, i musi wracać do tych węzłów. Algorytm Dijkstry relaksuje połączenia każdego węzła dokładnie raz, w chwili, gdy jego czas staje się ostateczny. Pytanie brzmi: skąd wiadomo, kiedy to następuje?

Odpowiedzią jest zachłanna reguła: spośród węzłów, które nie zostały jeszcze ustalone, ten o najmniejszym czasie tymczasowym ma już czas ostateczny. Każda inna trasa do niego musi w pewnym momencie opuścić ustalone węzły przez nieustalony węzeł, którego czas jest co najmniej tak duży, a dalsze połączenia mogą tylko zwiększyć czas, ponieważ żadne z nich nie ma ujemnej wartości. Ustalasz więc ten węzeł, relaksujesz jego połączenia i powtarzasz. W pierwszym przykładzie węzeł 1 zostaje ustalony w chwili 0 i oferuje węzłowi 2 czas 4, a węzłowi 3 czas 1. Węzeł 3 ma najmniejszy czas, zostaje ustalony w chwili 1 i obniża czas węzła 2 do 3. Węzeł 2 zostaje ustalony w chwili 3 i oferuje węzłowi 4 czas 4; ten zostaje ustalony jako ostatni. Odpowiedź to 4.

Kopiec minimalny szybko znajduje najmniejszy czas tymczasowy. Dodawaj (time, node) za każdym razem, gdy czas węzła ulega poprawie, a starszy wpis pozostaw w kopcu zamiast go wyszukiwać. Gdy starszy wpis zostanie później zdjęty z kopca, jego czas będzie większy od bieżącego czasu węzła, więc go pomijasz. Każde połączenie dodaje najwyżej jeden wpis, dlatego kopiec nigdy nie zawiera więcej niż E + 1 wpisów, a każde dodanie lub zdjęcie z kopca kosztuje O(log E). Łącznie daje to O(E log E), przy zużyciu O(n + E) pamięci na listę sąsiedztwa, czasy i kopiec.

Nieujemne czasy sprawiają, że zachłanna reguła jest bezpieczna. Rozważ połączenia A → B o czasie 2, A → C o czasie 3 oraz C → B o czasie -2. Algorytm Dijkstry ustala węzeł B w chwili 2, a jednak trasa przez C dociera do niego w chwili 1. Sygnał nigdy nie może dotrzeć przed wysłaniem, więc każdy czas w tym przypadku jest co najmniej równy 0 i reguła jest spełniona.