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

97

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?

anuj pradhan
źródło
5
To Dijkstra. „ij” to dwugłoska (samogłoska ślizgowa) w języku niderlandzkim i jest to jedyne miejsce, w którym „j” nie jest spółgłoską.
23
jakkolwiek masz to pytanie.
anuj pradhan,
4
Najlepszym sposobem na odróżnienie ich różnic jest przeczytanie kodu źródłowego , Dijkstry i Prim . Główna różnica jest tutaj: dla Prim graph[u][v] < key[v]i dla Dijkstry dist[u]+graph[u][v] < dist[v]. Jak więc widać na wykresach na tych dwóch stronach, różnią się one głównie z powodu tych dwóch wierszy kodu.
JW.ZG

Odpowiedzi:

151

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!

templatetypedef
źródło
Pierwszy akapit nie ma sensu, stary. Pytanie brzmi, jaka jest różnica między Dijkstrą a Prim, gdzie Dijkstra nie dotyczy tego, co powiedziałeś the length of a path between **any** two nodes, powinieneś po prostu skupić się na tym, dlaczego odległość między węzłem src a jakimikolwiek innymi węzłami w Prim nie jest najkrótsza, jeśli nie jest najkrótsza. Myślę, że musi prosić węzeł src w Prim do dowolnego innego węzła . Dlaczego wspomniałeś o dwóch dowolnych węzłach w Prim? To oczywiście nie jest najkrótsze.
JW.ZG
2
Wyczyściłem sformułowanie w akapicie o algorytmie Dijkstry, aby wyjaśnić, że drzewo najkrótszej ścieżki jest tylko minimalizatorem dla najkrótszych ścieżek pochodzących z węzła źródłowego. Powodem, dla którego ustrukturyzowałem moją odpowiedź w ten sposób, był sposób zilustrowania tego, co znajdują algorytmy, a nie tego, jak działają, aby pokazać na wyższym poziomie, dlaczego dają różne wyniki i dlaczego nie można oczekiwać, że będą takie same.
templatetypedef
1
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. Zobacz stackoverflow.com/a/51605961/6668734
Deepak Yadav,
1
@templatetypedef - kiedy mówisz: „a koszt budowy takiego drzewa [z Dijkstrą] może być znacznie większy niż koszt MST”. czy możesz to rozwinąć?
Amelio Vazquez-Reina
1
@ AmelioVazquez-Reina Przepraszamy, ten fragment jest niejednoznaczny. Chodziło mi o to, że suma wag na krawędziach drzewa o najkrótszych ścieżkach może być znacznie większa niż suma wag na krawędziach w MST.
templatetypedef
85

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.

dfb
źródło
2
Ok, dzięki ... wyczyściłeś dobry punkt do zauważenia. Do tej pory myślałem, że dane wyjściowe generowane przez dijkstrę będą MST, ale rozwiałeś wątpliwości na dobrym przykładzie Widzę wyraźnie, czy znajdę MST, używając powiedz `` kruskal '', wtedy uzyskam tę samą ścieżkę, o której wspomniałeś .
Wielkie
8
Bardziej poprawnie - The shortest path is 9... od s do t. Waga wykresu wygenerowanego przez algorytm Dijkstry, zaczynając od s, wynosi 14 (5 + 9).
Bernhard Barker,
1
@Dukeling - co? waga drzewa / wykresu u Dijkstry jest bez znaczenia, o to w pewnym sensie ....
dfb
4
Bardzo zwięźle zilustrowane!
Ram Narasimhan
1
@dfb: Zwykle używamy algorytmu Dijkstry tylko po to, aby uzyskać najkrótszą ścieżkę między określoną parą wierzchołków, ale w rzeczywistości możesz kontynuować, dopóki wszystkie wierzchołki nie zostaną odwiedzone, a to da ci "drzewo najkrótszej ścieżki", jako odpowiedź templatetypedef wyjaśnia.
j_random_hacker
65

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
Albert Chen
źródło
Na poziomie kodu inną różnicą jest API. Prim ma metodę edges()zwracania krawędzi MST, podczas gdy Dijkstra ma distanceTo(v), pathTo(v)która odpowiednio zwraca odległość od źródła do wierzchołka v i ścieżkę od źródła do wierzchołka v, gdzie s jest wierzchołkiem, którym zainicjowałeś Dijkstrę.
nethsix
1
Następstwem, inicjowanie Prim z dowolnego dowolnego źródła wierzchołka, s zwraca taką samą wyjście edges(), ale z różnych inicjalizacji Dijkstra s powróci innego wyjście distanceTo(v), pathTo(v).
nethsix
Czy prims dopuszczają ujemną wagę? jeśli tak, to jest to kolejna różnica. Czytałem, że możesz zezwolić na ujemne wagi na prim, dodając duże pozytywne nie. do każdej wartości, dzięki czemu wszystko jest pozytywne.
Akhil Dad
1
Rozwiązałem moje zamieszanie! Doskonała odpowiedź !!
Dhananjay Sarsonia
tutaj przetworzony wierzchołek musi zostać zignorowany dla grafu niekierowanego
pan AJ
53

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

fersarr
źródło
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. Zobacz stackoverflow.com/a/51605961/6668734
Deepak Yadav,
32

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.

Kevindra
źródło
24

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.

Shital Shah
źródło
Dzięki! Wyjście jest mgliste, dlaczego wychodzi z pętli, nawet jeśli nic się nie dzieje?
amirouche
15

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.
Rahul
źródło
10

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ę.

jestem zmieszany
źródło
5
„Dijkstra dotyczy tylko dwóch węzłów” to bzdura.
tmyklebu
5

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.

ccy
źródło
3

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.

象 嘉 道
źródło
3

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
user1732445
źródło
2

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.

Dynamiczny programista
źródło
2

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.

Deepak Yadav
źródło
0

@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.

Shital Shah
źródło
0

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).

nethsix
źródło