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 x 1, ale x 1 był aktualizowany po x 2 ?$x_2$$x_1$$x_1$$x_2$

Rozważ najkrótszą ścieżkę od do t , s , v 1 , v 2 , … , v k , t . Ta ścieżka składa się co najwyżej | V | - 1 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 v 1 będzie poprawne po tej rundzie. Zauważ, że nie mamy pojęcia, czym w tym momencie jest v 1 , ale ponieważ rozluźniliśmy wszystkie krawędzie, musieliśmy również złagodzić ten. W drugiej rundzie relaksujemy się ( v 1 , v 2 ) w pewnym momencie. Nadal nie mamy pojęcia, czym są v 1 lub v 2 , 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ę ( v k , t ) , po czym oszacowanie odległości dla t jest poprawne. Nie mamy pojęcia, czym jest k, 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 , i -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 | V | - 1 krawędź długa, | V | - 1 runda wystarczy, aby znaleźć tę najkrótszą ścieżkę. Jeśli | V | 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|$

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.