Minimalne drzewo opinające vs Najkrótsza ścieżka

Jaka jest różnica między algorytmem minimalnego drzewa opinającego a algorytmem najkrótszej ścieżki?

W mojej klasie struktur danych omówiliśmy dwa algorytmy minimalnego drzewa opinającego (Prim i Kruskala) oraz jeden algorytm najkrótszej ścieżki (Dijkstry).

Minimalne drzewo opinające to drzewo na wykresie, które obejmuje wszystkie wierzchołki, a całkowita waga drzewa jest minimalna. Najkrótsza ścieżka jest dość oczywista, jest to najkrótsza ścieżka od jednego wierzchołka do drugiego.

To, czego nie rozumiem, to to, że minimalne drzewo opinające ma minimalną całkowitą wagę, czy ścieżki w drzewie nie byłyby najkrótszymi ścieżkami? Czy ktoś może wyjaśnić, czego mi brakuje?

Każda pomoc jest mile widziana.

Rozważmy trójkąt z wagami jednostkowymi - ma trzy wierzchołki , a wszystkie trzy krawędzie { x , y } , { x , z } , { y , z } mają wagę 1 . Najkrótszą ścieżką między dowolnymi dwoma wierzchołkami jest ścieżka bezpośrednia, ale jeśli złożysz je wszystkie razem, otrzymasz trójkąt zamiast drzewa. Każda kolekcja dwóch krawędzi tworzy minimalne drzewo opinające na tym wykresie, ale jeśli (na przykład) wybierzesz { x , y } , { y $x,y,z$$\{x,y\},\{x,z\},\{y,z\}$$1$ , a następnie przegapisz najkrótszą ścieżkę { x , z } .$\{x,y\},\{y,z\}$$\{x,z\}$

Podsumowując, jeśli zestawisz wszystkie najkrótsze ścieżki razem, niekoniecznie otrzymasz drzewo.

Masz rację, że dwa algorytmy Dijkstry (najkrótsze ścieżki z jednego węzła początkowego) i Prim (drzewo rozpinające minimalną wagę zaczynające się od danego węzła) mają bardzo podobną strukturę. Obaj są zachłanni (z najlepszej strony z obecnego punktu widzenia) i budują drzewo na wykresie.

Wartość, którą minimalizują, jest jednak inna. Dijkstra wybiera jako następną krawędź tę, która prowadzi z drzewa do węzła, który nie został jeszcze wybrany najbliżej węzła początkowego. (Następnie przy tym wyborze odległości są ponownie obliczane.) Prim wybiera krawędź najkrótszej z dotychczas zbudowanych drzew. Tak więc oba algorytmy wybrały „minimalną przewagę”. Główną różnicą jest wartość wybrana jako minimalna. Dla Dijkstry jest to długość pełnej ścieżki od węzła początkowego do węzła kandydującego, dla Prim jest to tylko ciężar tej pojedynczej krawędzi.

$x,y,z$$\{x,y\}$$\{x,z\}$$\{y,z\}$$x$$\{x,y\}$$\{x,z\}$$\{x,y\}$$\{y,z\}$

Jeśli chodzi o Kruskala , to jest nieco inne. Rozwiązuje minimalne drzewo opinające, ale podczas wykonywania wybiera krawędź, która może nie tworzyć drzewa, po prostu unikają cykli. Częściowe rozwiązania mogą zostać rozłączone. W końcu dostajesz drzewo.

Chociaż obliczenia algorytmów minimalnego drzewa opinającego i najkrótszej ścieżki wyglądają podobnie, koncentrują się na 2 różnych wymaganiach.

W MST wymagane jest osiągnięcie każdego wierzchołka jeden raz (utworzenie drzewa wykresów), a całkowity (zbiorowy) koszt dotarcia do każdego wierzchołka musi być minimalny wśród wszystkich możliwych kombinacji.

W najkrótszej ścieżce wymagane jest dotarcie do wierzchołka docelowego z wierzchołka źródłowego przy możliwie najniższym koszcie (najkrótsza waga). Więc tutaj nie martwimy się o dotarcie do każdego wierzchołka, zamiast tego skupimy się tylko na wierzchołkach źródłowym i docelowym i na tym polega różnica.

Oto przykład wyjaśniający, dlaczego MST niekoniecznie podaje najkrótszą ścieżkę między 2 wierzchołkami.

(A)----5---(B)----5---(C)
 |                     |
 |----------7----------| 

W przypadku MST, krawędzie AB. BC będzie na MST o łącznej wadze 10. Zatem koszt dotarcia od A do C w MST wynosi 10.

Ale w przypadku najkrótszej ścieżki najkrótszą drogą od A do C jest AC, która wynosi 7. AC nigdy nie było na MST.

Różnica polega na tym, jaki jest ostateczny cel tych algorytmów

Dijkstra's - Tutaj celem jest dotarcie od początku do końca. Martwisz się tylko tymi 2 punktami i odpowiednio zoptymalizuj swoją ścieżkę.

Krusal's - Tutaj możesz zacząć od dowolnego punktu i musisz odwiedzić wszystkie inne punkty na wykresie. Dlatego nie zawsze możesz wybrać najkrótszą ścieżkę dla dwóch punktów. Zamiast tego nacisk kładziony jest na wybór ścieżki, która doprowadzi cię do krótszej ścieżki dla wszystkich innych punktów.

Myślę, że przykład to wyjaśni.

Drzewo rozpinające wygląda jak poniżej. Wynika to z tego, że jeśli dodamy krawędzie w tej konfiguracji, otrzymamy możliwie najmniejszy całkowity koszt : 2 + 5 + 14 + 4 = 25.

(1)   (4)
  \   /
   (2)
  /   \
(3)   (5)

Patrząc wzrokowo na drzewo rozpinające, możesz fałszywie myśleć, że daje ono najkrótsze ścieżki, ale w praktyce tak nie jest. Jako przykład, gdybyśmy chcieli przejść od węzła (1)do (4)niego, kosztowałoby nas to 7. Jednak gdybyśmy użyli algorytmu Dijkstry na oryginalnym wykresie, stwierdzilibyśmy, że możemy przejść bezpośrednio z węzła (1)do (4)kosztu 5.

Praktyczny przykład pokazujący różnicę>

Załóżmy, że przyjeżdżasz pociągiem do miasta i chcesz dostać się do hotelu.

Opcja 1: Weź taksówkę: Taksówka pojedzie najkrótszą drogą do hotelu z dworca. Jeśli kierowca powinien podążać ścieżką wzdłuż najkrótszej ścieżki drzewa wyśrodkowanej na stacji.

Opcja 2: wsiąść do autobusu. Firma autobusowa chce obsłużyć ludzi, nie tylko ciebie. Idealna ścieżka obejmowałaby wszystkie kluczowe punkty miasta. Będzie więc podążał (*) ścieżką wzdłuż minimalnego drzewa opinającego. Dlatego autobus jest wolniejszy, ale ponieważ koszty są dzielone, jest tańszy.

(*) W rzeczywistości ludzie narzekaliby, gdyby zastosowano minimalne drzewo opinające (podróż autobusem byłaby zbyt długa). Tak więc w praktyce byłoby to rozwiązanie mieszane i korzystałoby z drzewa alfa (w połowie odległości między minimalnym drzewem opinającym a drzewem najkrótszej ścieżki).

Opierają się na dwóch różnych właściwościach. Minimalne drzewo opinające opiera się na właściwości wycinania, podczas gdy najkrótsza ścieżka oparta jest na właściwości relaksacji krawędzi.

Cięcie dzieli wykres na dwa składniki. Może obejmować wiele krawędzi. W MST wybieramy krawędź o najmniejszej wadze.

Edge relaks mówi, że biorąc pod uwagę odległość między A i B: dist (a, b) i dist między A i C: dist (a, c), jeśli dist (a, b) + edge (b, c) jest mniejsza niż dist (a, c), a następnie mogę się zrelaksować edge (ac). Po rozluźnieniu wszystkich krawędzi uzyskujemy najkrótszą ścieżkę.

Gorąco polecam obejrzenie wideo na algorytmach grafowych od profesora Roberta Sedgewicka.