Přeskočit na obsah

Primov algoritmus: Rozdiel medzi revíziami

Odobraných 14 bajtov ,  pred 11 rokmi
preklepy
d (fix.)
(preklepy)
'''Primov algoritmus ''' (známy aj ako '''Jarníkov algoritmus''', '''Primov-Jarníkov algoritmus''' alebo aj '''DJP algoritmus''') je v informatike [[pažravý algoritmus|greedy algoritmus]] hľadajúci minimálnu kostru ohodnoteného grafu. Nájde teda takú podmnožinu hrán grafu, ktorá tvorí [[strom (graf)|strom]] obsahujúci všetky vrcholy pôvodného grafu a súčet ohodnotenia hrán z tejto množiny je minimálny. Algoritmus patrí medzi najefektívnejšie a najelegantnejšie implementovateľné algoritmy s týmto účelom. Prvýkrát algoritmus popísal český matematik [[Vojtěch Jarník]] roku [[1930]]. V roku [[1957]] tento algoritmusho nezávisle na Jarníkovi popísal americký matematik a informatik Robert Clay Prim a potom ešte raz v roku [[1959]] tento algoritmus znovu objavil holandský informatik [[Edsger Wybe Dijkstra]] a na jeho základe vytvoril svoj [[Dijkstrov algoritmus]] na hľadanie najkratšej cesty v ohodnotenom grafe.
 
== Popis ==
47

úprav