Algorytm Bellmana-Forda - Dlaczego krawędzie mogą być aktualizowane poza kolejnością?

Algorytm Bellmana-Ford, określa najkrótszą ścieżkę ze źródła, do pozostałych wierzchołków. Początkowo odległość między a wszystkimi innymi wierzchołkami jest ustawiona na . Następnie obliczana jest najkrótsza ścieżka od do każdego wierzchołka; dzieje się tak w przypadku iteracji . Moje pytania to: $s$ $s$ $\infty$ $s$ $|V|-1$

Dlaczego potrzebne są iteracje ? $|V|-1$
Czy miałoby to znaczenie, jeśli sprawdzę krawędzie w innej kolejności?
Powiedzmy, jeśli najpierw sprawdzę krawędzie 1,2,3, ale potem przy drugiej iteracji sprawdzę 2,3,1.

MIT Prof. Eric powiedział, że kolejność nie ma znaczenia, ale to mnie myli: czy algorytm niepoprawnie aktualizowałby węzeł oparty na krawędzi gdyby jego wartość była zależna od krawędzi ale był aktualizowany po ? $x_2$ $x_1$ $x_1$ $x_2$

algorithms shortest-path

— użytkownik1675999
źródło

Które wdrożenie rozważasz? Programowanie dynamiczne oczywiście nie ma problemu z porządkiem; dla innych może być nietrywialne.

— Raphael

Odpowiedzi:

Rozważ najkrótszą ścieżkę od do , . Ta ścieżka składa się co najwyżej krawędzie, ponieważ powtarzanie wierzchołka na najkrótszej ścieżce jest zawsze złym pomysłem (lub przynajmniej istnieje najkrótsza ścieżka, która nie powtarza wierzchołków), jeśli nie mamy ujemnych cykli wagi. $s$ $t$ $s, v_1, v_2, \dots, v_k, t$ $|V|-1$

W pierwszej rundzie wiemy, że krawędź zostanie rozluźniona, więc oszacowanie odległości dla będzie poprawne po tej rundzie. Zauważ, że nie mamy pojęcia, czym w tym momencie jest , ale ponieważ rozluźniliśmy wszystkie krawędzie, musieliśmy również złagodzić ten. W drugiej rundzie relaksujemy się w pewnym momencie. Nadal nie mamy pojęcia, czym są lub , ale wiemy, że ich szacunki odległości są prawidłowe. $(s, v_1)$ $v_1$ $v_1$ $(v_1, v_2)$ $v_1$ $v_2$

Powtarzając to, po pewnym okrążeniu rozluźniliśmy się , po czym oszacowanie odległości dla jest poprawne. Nie mamy pojęcia, czym jest dopóki nie skończy się cały algorytm, ale wiemy, że to się stanie w pewnym momencie (zakładając brak ujemnych cykli masy). $k+1$ $(v_k, t)$ $t$ $k$

Zatem kluczową obserwacją jest to, że po rundzie , -ty węzeł najkrótszej ścieżki musi mieć ustawione oszacowanie odległości na prawidłową wartość. Ponieważ ścieżka jest co najwyżej krawędź długa, runda wystarczy, aby znaleźć tę najkrótszą ścieżkę. Jeśli runda wciąż coś zmienia, potem dzieje się coś dziwnego: wszystkie ścieżki powinny już zostać „ustalone” do ich ostatecznych wartości, więc musimy mieć sytuację, w której istnieje pewien ujemny cykl wagowy. $i$ $i$ $|V|-1$ $|V|-1$ $|V|$

— Alex ten Brink
źródło

Mam tutaj małe wątpliwości. Uważam, że | v | -1 jest najgorszym przypadkiem liczby rund, po których obliczana jest najkrótsza ścieżka od s do t. Załóżmy, że mamy wierzchołki s, v1, v2..vn, t. krawędzie są wybierane w tej kolejności, powiedzmy (s, v1), (v1, v2) .. (vn, t), a następnie w samej iteracji będziemy mieli najkrótszą ścieżkę od s do t. To jest tylko dla zrozumienia i w warunki praktyczne nie znamy kolejności wybierania krawędzi, a zatem rund | v | -1. Mam rację?

— whokares,

@whokares: tak, możesz mieć szczęście i znaleźć najkrótszą ścieżkę w pierwszej rundzie. Do ostatniej rundy nie wiesz na pewno, że znaleziona wartość jest najkrótszą ścieżką, ale może być. Algorytm Dijkstry zasadniczo „powoduje”, że tak się dzieje: jeśli wszystkie krawędzie mają nieujemne wagi, kolejka priorytetowa zastosowana w algorytmie Dijkstry „przewiduje” kolejność, w której należy rozluźniać krawędzie, aby znaleźć wszystkie najkrótsze ścieżki w pierwszej rundzie relaksacji.

— Alex ten Brink,

Dzięki za aktualizację. Mam go. W jednym z materiałów wspomniano jako <br> Slajd 6: Zły wybór kolejności relaksacji może prowadzić do wykładniczo wielu relaksacji: <br> Slajd 8: „Inteligentna” kolejność relaksacji krawędzi <br>

— whokares 12.12.12

Niezależnie od kolejności krawędzi w każdej iteracji, Najkrótsze ścieżki będą obliczane w iteracjach | v | -1, prawda? Dlaczego on mówi wykładniczo. Czy to znaczy, że jeśli wybraliśmy tę samą kolejność dla wszystkich iteracji, co zwykle robimy, kod relaksacyjny zostanie wywołany, ale aktualizacja etykiety dla wierzchołka może się zdarzyć tylko kilka razy z powodu kolejności, oszczędzając w ten sposób procesor czas

— whokares 12.12.12

@whokares: pierwszy przedstawiony przez nich algorytm (który może mieć wykładniczy czas działania) nie rozluźnia wszystkich krawędzi w rundzie, ale zamiast tego znajduje krawędź, dla której operacja relaksacji coś zmieni i rozluźni tę krawędź. Jeśli nadal będziesz to robić i nie będzie ujemnego cyklu wagowego, to w końcu żadne krawędzie nie pomogą ci więcej i przestaniesz. Ponieważ jednak nie masz rund i nie ustawiasz kolejności, na której krawędzi dalej się zrelaksujesz, możesz w końcu wykonać wykładniczą liczbę relaksacji. Ulepszony algorytm, który prezentują, to Bellman-Ford, który ma rundy.

— Alex ten Brink,

Najdłuższa ścieżka może być bez cykli |V|. Zaczynamy od źródła, więc mamy już ścieżkę o długości 1, więc potrzebujemy |V| - 1więcej węzłów, aby uzyskać najdłuższą ścieżkę.

Kolejność nie ma znaczenia, ponieważ każde zamówienie zachowa niezmienność: po niteracjach wartość dla każdego węzła jest mniejsza lub równa kosztowi ścieżki minimalnego kosztu sdo węzła zawierającego co najwyżej nkrawędzie.

Jeśli na początku iteracji koszt jest poprawny do nwęzłów, to na końcu iteracji jest poprawny do n+1węzłów. Zmiana kolejności może spowodować, że niektóre węzły będą miały niższy koszt, zanim zostaną normalnie zaktualizowane, ale ostatecznie i tak zostaną zaktualizowane.

— FGB
źródło

Nie wiem, czy to tylko ja, czy nie jestem w stanie łatwo wyobrazić sobie tych faktów. Dla mnie nadal myślę, że mogą istnieć niektóre węzły, które nie zostały zaktualizowane w ramach iteracji V-1.

— user1675999,

Nie, masz | E | = | V | -1 krawędzi, gdy masz | V | węzły połączone prostą ścieżką bez cykli. I masz iteracje | V | -1, usuń swoją odpowiedź, ponieważ jest niepoprawna.

— Sam

@sam Kim jesteś i co ma wspólnego z odpowiedzią?

— fgb