Algorytm Prima

Algorytm Prima lub algorytm Dijkstry–Prima – algorytm zachłanny wyznaczający tzw. minimalne drzewo rozpinające (MDR). Mając do dyspozycji graf nieskierowany i spójny, tzn. taki w którym krawędzie grafu nie mają ustalonego kierunku oraz dla każdych dwóch wierzchołków grafu istnieje droga pomiędzy nimi, algorytm oblicza podzbiór E' zbioru krawędzi E, dla którego graf nadal pozostaje spójny, ale suma kosztów wszystkich krawędzi zbioru E' jest najmniejsza możliwa.Multigrafy (grafy o krawędziach "równoległych", w których dwa wierzchołki mogą być połączone kilkoma krawędziami) oraz grafy, w których pomiędzy niektórymi wierzchołkami istnieje wiele dróg o tej samej długości, raczej nie są "lubiane" przez algorytmy; często przekształcenie takiego grafu w graf mu równoważny pod względem zachowania możliwych połączeń przynosi znaczące korzyści Algorytm Prima wygląda tak:Niech dany będzie graf oraz dwa algorytmy: algorytm Prima oraz niezachłanny i poprawny algorytm znajdowania MDR. Załóżmy, że drzewo spinające znalezione przez algorytm Prima nie jest minimalne.Zakładamy, że drugi algorytm, podobnie jak algorytm Prima pobiera kolejne gałęzie grafu wejściowego, dołączając je do początkowo pustego drzewa wynikowego (odpowiednio Tp i Topt). Załóżmy, że dla pierwszych i gałęzi algorytmy zadziałały tak samo, tj.krawędzie i są różne.Niech oznacza zbiór wierzchołków grafu G połączonych krawędziami .Ponieważ wybór e był niezachłanny, to waga e jest nie większa niż waga f.Niechco jest sprzeczne z wyborem .Podobne rozumowanie można przeprowadzić dla kolejnych dołączanych do drzew wynikowych krawędzi.Wniosek – nie może istnieć drzewo spinające o sumie wag mniejszej, niż drzewo odnalezione algorytmem Primaalgorytm Prima zawsze odnajduje minimalne drzewo spinające.