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 + 1
co 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.