Dijkstrov algoritmus: Rozdiel medzi revíziami

Dijkstrov algoritmus je jedným zo základných [[Algoritmus|algoritmov]] [[Teória grafov|teórie grafov]], jeho primárnym využitím je hľadanie najkratšej cesty v hranovo-ohodnotenom [[Graf (matematika)|digrafe]] ''G = (V, H, c)''. Tento graf pozostáva z [[množina|množiny]] vrcholov ''V'', množiny orientovaných hrán ''H'' a [[Zobrazenie (matematika)|funkcie]] ''c'', ktorá zobrazuje množinu hrán do množiny [[Reálne číslo|reálnych čísel]]. Teda pre ňu platí ''H → R''. Ďalším predpokladom je aby ''c(h) ≥ 0'', pre všetky hrany ''h'' z množiny ''H''. Jeho autorom je holandský matematik [[Edsger Wybe Dijkstra|E. W. Dijkstra]] a typovo ide o algoritmus najkratšej cesty z jedného vrcholu (počiatok, označme ho aj ''s'') do ostatných, najčastejšie však do jedného konkrétneho (cieľ ''d'').

* ''t(v)'' = ∞, pre všetky ''v ≠ s''; ''t(s)'' = 0,

* ''x(v)'' = 0, pre všetky ''v'' z ''V'',

* ''p(v)'' = false, pre všetky ''v ≠ s''; ''p(s)'' = true,

Vo všetkých behoch prvého kroku sa vykoná maximálne ''|H|'' = ''m'' [[Matematická operácia|operácií]], keďže každú hranu použijeme nanajvýš raz. V druhom kroku stačí prezrieť maximálne ''|V|'' = ''n'' vrcholov. [[Výpočtová zložitosť]] Dijkstrovho algoritmu je teda ''O(n²)''.