Czy algorytm dijkstras rozluźnia krawędzie najkrótszej ścieżki w kolejności?

Question

W "Wprowadzenie do algorytmów, 3rd edition" ćwiczenia 24.3-5 chce przykład, że jest to złe (nie zawsze prawdziwe). Czy to jest możliwe? Moim zdaniem jest to niemożliwe, ponieważ każda krawędź jest rozluźniona w momencie, gdy już podjęto decyzję o ścieżce do obecnego wierzchołka.

Słowo w słowo:

Profesor N. twierdzi, że ma dowód poprawności algorytmu Dijkstry. Twierdzi, że algorytm Dijkstry rozluźnia krawędzie każdej najkrótszej ścieżki na wykresie w kolejności, w jakiej pojawiają się na ścieżce, a zatem własność relacyjno-ścieżkowa odnosi się do każdego wierzchołka osiągalnego ze źródła. Pokaż, że profesor myli się, konstruując skierowany wykres, dla którego algorytm Dijkstry może rozluźnić krawędzie najkrótszej ścieżki nieporządku.

Answer 1

Myślę, że kluczem wyrażenie w brzmieniu, jest to, że Algorytm Dijkstry „rozluźnia krawędzie każdy Najkrótsza ścieżka w grafie ...”

Że sam jest kłamstwem jeśli istnieje wiele najkrótszych ścieżkach taki sam koszt.

Weź pod uwagę ten wykres: A -> B, A -> C, B -> D, C -> D. Źródło to A, a miejsce docelowe to D. Każda waga krawędzi wynosi 1. Istnieją dwie ścieżki od A do D, jeden do B i jeden do C. Jednak jedna krawędź B-> D lub C-> D nigdy nie ulega rozluźnieniu.

Nadal nie jesteś przekonany, ponieważ dijkstra kończy się przed oceną drugiej krawędzi na D? Wrzuć dodatkową krawędź D-> E i ustaw cel na E. Ścieżka od A-> D do B jest taka sama, jak A-> D do C i oba są tańsze niż koszt z A-> E. Jednak nigdy nie rozluźnisz drugiej krawędzi D, ponieważ algorytm rozluźnia tylko krawędzie do wierzchołków, które nie znają jeszcze najkrótszej ścieżki.

Answer 2

Wykonaj pojedynczą krawędź o wadze 3, która dociera do miejsca docelowego. Teraz dodaj ścieżkę składającą się z kilku przystanków, o łącznej wadze mniejszej niż trzy, która również dotrze do celu. Kiedy rozluźnisz pochodzenie, pokolorujesz węzeł docelowy jako trzy, co jest błędne. Musisz kontynuować relaksowanie wszystkich węzłów bliżej niż (min znanej ścieżki do miejsca docelowego), dopóki ten zestaw nie będzie pusty. Tylko wtedy możesz być pewien, że algorytm D dał ci poprawną odpowiedź.

Wyszukaj algorytm A * dla większej zabawy.

Answer 3

Chodzi o to, że wniosek nie wynika z przesłanek i skonstruowania kontrprzykładu. SSSP znajduje wszystkie najkrótsze ścieżki. Nie ma powodu, aby najkrótsze ścieżki musiały znajdować się w ścisłej kolejności. Rozważmy drzewo-wykres. Wszystkie ścieżki są również najkrótsze. Teraz, jeśli rozluźnimy korzeń, wtedy nie ma żadnego szczególnego porządku na krawędziach. Ale załóżmy, że nawet nałożyłeś jeden. Następnie, po rozluźnieniu najbliższego węzła innego niż root, możesz mieć sporo naprawdę długich krawędzi do drugiej warstwy. Najbliższy najbliższy sąsiad może mieć kilka naprawdę krótkich krawędzi wychodzących do tej części drugiej warstwy. W takim przypadku rozluźnisz krawędzie, które przyczyniają się do całkowitej długości ścieżki SHORTER, niż innych krawędzi, które już zostały rozluźnione, ponieważ zawsze rozluźniasz się, nie rozdzielając krawędzi, w kolejności najkrótszej ścieżki.

Answer 4

Należy wziąć pod uwagę następujący wykres: (A, B), (A, C), (B, D), (C, D), (D, E) o wadze krawędzi w (A, B) = 1 , w (A, C) = 1, w (B, D) = 0, w (C, D) = 0, w (D, E) = 1. Źródłem wierzchołka jest A. Możliwe permutacja krawędzi złagodzone w Algorytm Dijkstry to (A, B), (A, C), (B, D), (D, E), (C, D). Poza tym A.d = 0, B.d = 1, C.d = 1, D.d = 1, E.d = 2 po wykonaniu algorytmu Dijkstry. Istnieją dwie najkrótsze ścieżki od A do E, jedna to ABDE, a druga to ACDE.Sprzeczność jest z drugą ścieżką, krawędź (C, D) powinna być zawsze zrelaksowana przed (D, E).

Answer 5

Rozważmy wykresu:

A--->B A--->C B--->C C--->D 

i niech każde ostrze ma ciężar 0.

algorytm Dijkstry może rozluźnić krawędzi w celu

(A,C) (A,B) (C,D) (B,C) 

wykres dwa najkrótszych ścieżek z Od A do D, oba kosztują 0,

A-->B-->C-->D or A-->C-->D 

Krawędzie najkrótszej ścieżki {A -> B -> C -> D} są spokojniejsze, ponieważ (B, C) są zrelaksowane PO (C, D).