Różnica między algorytmami Prim i Dijkstra?

Jaka jest dokładna różnica między algorytmami Dijkstry i Prim? Wiem, że Prim poda MST, ale drzewo wygenerowane przez Dijkstrę będzie również MST. Więc jaka jest dokładna różnica?

Algorytm Prima konstruuje minimalne drzewo rozpinające dla grafu, które jest drzewem, które łączy wszystkie węzły na grafie i ma najmniejszy całkowity koszt spośród wszystkich drzew łączących wszystkie węzły. Jednak długość ścieżki między dowolnymi dwoma węzłami w MST może nie być najkrótszą ścieżką między tymi dwoma węzłami na oryginalnym wykresie. MST są przydatne, na przykład, jeśli chcesz fizycznie połączyć węzły na wykresie, aby zapewnić im energię elektryczną po najmniejszym całkowitym koszcie. Nie ma znaczenia, że ​​długość ścieżki między dwoma węzłami może nie być optymalna, ponieważ zależy Ci tylko na tym, że są połączone.

Algorytm Dijkstry konstruuje najkrótsze drzewo ścieżek, zaczynając od jakiegoś węzła źródłowego. Drzewo najkrótszej ścieżki to drzewo, które łączy wszystkie węzły na grafie z powrotem do węzła źródłowego i ma właściwość polegającą na tym, że długość dowolnej ścieżki od węzła źródłowego do dowolnego innego węzła na wykresie jest zminimalizowana. Jest to przydatne, na przykład, jeśli chcesz zbudować sieć drogową, która zapewniłaby każdemu możliwie najbardziej efektywne dotarcie do jakiegoś ważnego punktu orientacyjnego. Nie ma jednak gwarancji, że drzewo o najkrótszej ścieżce będzie minimalnym drzewem rozpinającym, a suma kosztów na krawędziach drzewa o najkrótszej ścieżce może być znacznie większa niż koszt MST.

Kolejna ważna różnica dotyczy typów grafów, na których pracują algorytmy. Algorytm Prima działa tylko na grafach nieukierunkowanych, ponieważ koncepcja MST zakłada, że ​​grafy są z natury nieukierunkowane. (W przypadku grafów skierowanych istnieje coś, co nazywa się „minimalną rozpiętością arborescencji”, ale algorytmy ich wyszukiwania są znacznie bardziej skomplikowane). Algorytm Dijkstry będzie działał dobrze na ukierunkowanych grafach, ponieważ drzewa o najkrótszej ścieżce można rzeczywiście skierować. Ponadto algorytm Dijkstry niekoniecznie daje prawidłowe rozwiązanie na grafach zawierających ujemne wagi krawędzi , podczas gdy algorytm Prima może sobie z tym poradzić.

Mam nadzieję że to pomoże!

Algorytm Dijkstry nie tworzy MST, znajduje najkrótszą ścieżkę.

Rozważ ten wykres

       5     5
  s *-----*-----* t
     \         /
       -------
         9

Najkrótsza ścieżka to 9, podczas gdy MST to inna „ścieżka” w 10.

Algorytmy Prim i Dijkstra są prawie takie same, z wyjątkiem „funkcji relaksacji”.

Sztywny:

MST-PRIM (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v)    <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

Dijkstra:

Dijkstra (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v) + u.key  <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

Jedyną różnicę wskazuje strzałka, czyli funkcja relaksu.

• Prim, który wyszukuje minimalne drzewo rozpinające, dba tylko o to, aby całkowita liczba krawędzi obejmowała wszystkie wierzchołki. Funkcja relaksu jestalt = w(u,v)
• Dijkstra, która wyszukuje minimalną długość ścieżki, więc dba o gromadzenie się krawędzi. Funkcja relaksu jestalt = w(u,v) + u.key

Algorytm Dijsktry znajduje minimalną odległość od węzła i do wszystkich węzłów (określasz i). W zamian otrzymujesz drzewo minimalnej odległości od węzła i.

Algorytm Prims pozwala uzyskać minimalne drzewo rozpinające dla danego wykresu . Drzewo, które łączy wszystkie węzły, a suma wszystkich kosztów to minimum.

Dzięki Dijkstra możesz przejść z wybranego węzła do dowolnego innego przy minimalnym koszcie , nie dostaniesz tego z Prim's

Jedyną różnicą, jaką widzę, jest to, że algorytm Prima przechowuje minimalną granicę kosztów, podczas gdy algorytm Dijkstry przechowuje całkowity koszt od wierzchołka źródłowego do bieżącego wierzchołka.

Dijkstra umożliwia przejście od węzła źródłowego do węzła docelowego, tak aby koszt był minimalny. Jednak algorytm Prim zapewnia minimalne drzewo opinające, tak aby wszystkie węzły były połączone, a całkowity koszt był minimalny.

W prostych słowach:

Tak więc, jeśli chcesz wdrożyć pociąg, który połączy kilka miast, użyj algorytmu Prim. Ale jeśli chcesz podróżować z jednego miasta do drugiego, oszczędzając jak najwięcej czasu, użyj algo Dijkstry.

Oba można zaimplementować przy użyciu dokładnie tego samego algorytmu ogólnego:

Inputs:
  G: Graph
  s: Starting vertex (any for Prim, source for Dijkstra)
  f: a function that takes vertices u and v, returns a number

Generic(G, s, f)
    Q = Enqueue all V with key = infinity, parent = null
    s.key = 0
    While Q is not empty
        u = dequeue Q
        For each v in adj(u)
            if v is in Q and v.key > f(u,v)
                v.key = f(u,v)
                v.parent = u

Dla Prim - pass f = w(u, v)i dla Dijkstra pass f = u.key + w(u, v).

Inną interesującą rzeczą jest to, że powyżej Generic może również zaimplementować Breadth First Search (BFS), chociaż byłoby to przesada, ponieważ droga kolejka priorytetów nie jest tak naprawdę wymagana. Aby włączyć powyższy algorytm Generic do BFS, należy przejść, f = u.key + 1co jest tym samym, co wymuszenie wszystkich wag na 1 (tj. BFS podaje minimalną liczbę krawędzi wymaganych do przejścia z punktu A do B).

Intuicja

Oto jeden dobry sposób na przemyślenie powyższego ogólnego algorytmu: Zaczynamy od dwóch segmentów A i B. Początkowo umieść wszystkie swoje wierzchołki w B, aby wiadro A było puste. Następnie przesuwamy jeden wierzchołek z B do A. Teraz spójrz na wszystkie krawędzie z wierzchołków w A, które przecinają się z wierzchołkami w B. Wybraliśmy jedną krawędź, używając pewnych kryteriów z tych przecinających się krawędzi i przesuwamy odpowiedni wierzchołek z B do A. Powtarzaj ten proces, aż B będzie pusty.

Brutalnym sposobem realizacji tego pomysłu byłoby utrzymanie kolejki priorytetowej krawędzi dla wierzchołków w A, które przecinają się do B. Oczywiście byłoby to kłopotliwe, gdyby wykres nie był rzadki. Więc pytanie brzmi: czy możemy zamiast tego zachować kolejkę priorytetową wierzchołków? W rzeczywistości możemy, ponieważ naszą ostateczną decyzją jest, który wierzchołek wybrać z B.

Kontekst historyczny

Interesujące jest to, że ogólna wersja techniki stojącej za obydwoma algorytmami jest koncepcyjnie tak stara jak 1930, nawet kiedy nie było komputerów elektronicznych.

Historia zaczyna się od Otakara Borůvki, który potrzebował algorytmu dla przyjaciela rodziny, próbującego dowiedzieć się, jak połączyć miasta w kraju Moraw (obecnie część Czech) przy minimalnych kosztach liniami elektrycznymi. Opublikował swój algorytm w 1926 roku w czasopiśmie związanym z matematyką, ponieważ informatyka wtedy nie istniała. Zwrócił na to uwagę Vojtěch Jarník, który pomyślał o ulepszeniu algorytmu Borůvki i opublikował go w 1930 roku. W rzeczywistości odkrył ten sam algorytm, który znamy teraz jako algorytm Prima, który odkrył go ponownie w 1957 roku.

Niezależnie od tego wszystkiego, w 1956 roku Dijkstra musiał napisać program, który zademonstruje możliwości nowego komputera opracowanego przez jego instytut. Pomyślał, że fajnie byłoby mieć połączenie komputerowe do podróżowania między dwoma miastami w Holandii. Zaprojektował algorytm w 20 minut. Stworzył wykres 64 miast z pewnymi uproszczeniami (ponieważ jego komputer był 6-bitowy) i napisał kod dla tego komputera z 1956 roku. Jednak nie opublikował swojego algorytmu, ponieważ przede wszystkim nie było czasopism informatycznych i pomyślał, że może to nie być bardzo ważne. W następnym roku dowiedział się o problemie podłączania zacisków nowych komputerów tak, aby zminimalizować długość przewodów. Przemyślał ten problem i ponownie odkrył Jarník / Prim ' s algorytm, który ponownie wykorzystuje tę samą technikę, co algorytm najkrótszej ścieżki, jaki odkrył rok wcześniej. Onwspomniał, że oba jego algorytmy zostały zaprojektowane bez użycia pióra lub papieru. W 1959 roku opublikował oba algorytmy w artykule o długości zaledwie 2 i pół strony.

Dijkstra znajduje najkrótszą ścieżkę między swoim początkowym węzłem a każdym innym węzłem. W zamian otrzymujesz drzewo minimalnej odległości od węzła początkowego, czyli możesz dotrzeć do każdego innego węzła tak efektywnie, jak to tylko możliwe.

Algorytm Prims pobiera MST dla danego grafu, czyli drzewa, które łączy wszystkie węzły, a suma wszystkich kosztów to minimum.

Aby opowieść krótką z realistycznym przykładem:

1. Dijkstra chce znać najkrótszą drogę do każdego punktu docelowego, oszczędzając czas podróży i paliwo.
2. Prim chce wiedzieć, jak efektywnie wdrożyć system kolei, czyli oszczędzić koszty materiałów.

Bezpośrednio z artykułu Dijkstra's Algorithm w Wikipedii:

Proces leżący u podstaw algorytmu Dijkstry jest podobny do zachłannego procesu używanego w algorytmie Prima. Celem Prim jest znalezienie minimalnego drzewa opinającego, które łączy wszystkie węzły na grafie; Dijkstra dotyczy tylko dwóch węzłów. Prim's nie ocenia całkowitej wagi ścieżki od węzła początkowego, tylko indywidualną ścieżkę.

Ostatnio zadawało mi to samo pytanie i myślę, że mogę podzielić się swoim zrozumieniem ...

Myślę, że kluczowa różnica między tymi dwoma algorytmami (Dijkstra i Prim) tkwi w problemie, który mają rozwiązać, a mianowicie w najkrótszej ścieżce między dwoma węzłami i minimalnym drzewie rozpinającym (MST). Formalne jest znalezienie najkrótszej ścieżki między powiedzmy, węzłem s i t , a racjonalnym wymogiem jest odwiedzenie każdej krawędzi wykresu co najwyżej raz. Jednak NIE wymaga od nas odwiedzania wszystkich węzłów. Ta ostatnia (MST) ma skłonić nas do odwiedzenia WSZYSTKICH węzłów (najwyżej raz) i przy tym samym racjonalnym wymogu odwiedzenia każdej krawędzi co najwyżej raz.

To powiedziawszy, Dijkstra pozwala nam „iść na skróty” tak długo, że mogę przejść od s do t , bez martwienia się o konsekwencje - kiedy dotrę do t , to koniec! Chociaż istnieje również ścieżka od s do t w MST, ale ta ścieżka s - t jest tworzona z uwzględnieniem wszystkich pozostałych węzłów, dlatego ścieżka ta może być dłuższa niż ścieżka s - t znaleziona przez algorytm Dijstry. Poniżej znajduje się szybki przykład z 3 węzłami:

                                  2       2  
                          (s) o ----- o ----- o (t)     
                              |               |
                              -----------------
                                      3

Powiedzmy, że każda z górnych krawędzi kosztuje 2, a dolna 3, wtedy Dijktra powie nam, żebyśmy wybrali dolną ścieżkę, ponieważ nie obchodzi nas środkowy węzeł. Z drugiej strony Prim zwróci nam MST z 2 górnymi krawędziami, odrzucając dolną krawędź.

Taka różnica jest również odzwierciedlona subtelną różnicą w implementacjach: w algorytmie Dijkstry trzeba mieć krok księgowania (dla każdego węzła), aby zaktualizować najkrótszą ścieżkę z s , po wchłonięciu nowego węzła, podczas gdy w algorytmie Prima nie ma takiej potrzeby.

Kluczowa różnica między podstawowymi algorytmami polega na ich różnych kryteriach wyboru krawędzi. Zasadniczo oba używają kolejki priorytetowej do wybierania kolejnych węzłów, ale mają różne kryteria wyboru sąsiednich węzłów bieżących węzłów przetwarzania: Algorytm Prim wymaga, aby następne sąsiednie węzły również były przechowywane w kolejce, podczas gdy algorytm Dijkstry nie:

def dijkstra(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            ...

def prim(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            if v in q and weight(u, v) < v.distance:// <-------selection--------
            ...

Obliczenia odległości wierzchołków to drugi inny punkt.

Algorytm Dijkstry to problem najkrótszej ścieżki z jednego źródła między węzłem i i j, ale algorytm Prima to minimalny problem drzewa rozpinającego. Te algorytmy wykorzystują koncepcję programowania zwaną „algorytmem chciwym”

Jeśli zaznaczysz te pojęcie, odwiedź

1. Notatka z wykładu Greedy Algorytm: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-greedy.pdf
2. Minimalne drzewo rozpinające: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/20-mst.pdf
3. Najkrótsza ścieżka z jednego źródła: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/21-sssp.pdf

Algorytm Dijkstrasa służy tylko do znajdowania najkrótszej ścieżki.

W drzewie minimalnym rozpinającym (algorytm Prima lub Kruskala) otrzymujesz minimalne egdes z minimalną wartością krawędzi.

Na przykład: - Rozważ sytuację, w której nie chcesz utworzyć ogromnej sieci, dla której będziesz potrzebował dużej liczby przewodów, więc zliczanie przewodów można wykonać za pomocą minimalnego drzewa rozpinającego (algorytm Prima lub Kruskala) (tj. zapewniają minimalną liczbę przewodów do tworzenia ogromnych połączeń sieciowych przy minimalnych kosztach).

Natomiast „algorytm Dijkstrasa” zostanie użyty do uzyskania najkrótszej ścieżki między dwoma węzłami podczas łączenia ze sobą dowolnych węzłów.

Najprostszym wyjaśnieniem jest to, że w Prims nie określasz węzła początkowego, ale w dijsktra (potrzebujesz węzła początkowego) musisz znaleźć najkrótszą ścieżkę z danego węzła do wszystkich innych węzłów.

@templatetypedef omówił różnicę między MST a najkrótszą ścieżką. Omówiłem różnicę algorytmów w innej odpowiedzi So , demonstrując, że oba można zaimplementować przy użyciu tego samego algorytmu ogólnego, który przyjmuje jeszcze jeden parametr jako dane wejściowe: funkcję f(u,v). Różnica między algorytmem Prim i Dijkstry polega na tym, f(u,v)że po prostu używasz.

Na poziomie kodu inną różnicą jest API.

Inicjalizujesz Prim z wierzchołkiem źródłowym, s , tj Prim.new(s).; s może być dowolnym wierzchołkiem i niezależnie od s , wynik końcowy, którym są krawędzie minimalnego drzewa rozpinającego (MST), jest taki sam. Aby uzyskać krawędzie MST, wywołujemy metodę edges().

Inicjalizujesz Dijkstrę z wierzchołkiem źródłowym, s , tj. Dijkstra.new(s)Chcesz uzyskać najkrótszą ścieżkę / odległość do wszystkich innych wierzchołków. Wyniki końcowe, które są najkrótszą ścieżką / odległością od s do wszystkich innych wierzchołków; różnią się w zależności od s . Aby uzyskać najkrótsze ścieżki / odległości od s do dowolnego wierzchołka, v , wywołujemy odpowiednio metody distanceTo(v)i pathTo(v).