Primov algoritmus: Rozdiel medzi revíziami

Pridaných 8 bajtov ,  pred 11 rokmi
wikilinky
(aktualizácia)
(wikilinky)
'''Primov algoritmus ''' (známy aj ako '''Jarníkov algoritmus''', '''Primov-Jarníkov algoritmus''' alebo aj '''DJP algoritmus''') je v teórii grafov algoritmus hľadajúci minimálnu kostru ohodnoteného grafu. Nájde teda takú podmnožinu hrán grafu, ktorá tvorí 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 algoritmus 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