Efektívne algoritmy a zložitosť - 08 - Dijkstrov algoritmus

Zhrnutie prednášky

Prednáška najprv rekapituluje tri základné techniky tvorby efektívnych algoritmov: greedy algoritmy, dynamické programovanie a metódu rozdeľuj a panuj, spolu s typickými príkladmi a ich zložitosťami. Následne otvára novú tému, algoritmy na grafoch, a pripomína základné pojmy: vrcholy, hrany, orientované a neorientované grafy, váhované grafy a reprezentáciu maticou susednosti a zoznamami susedov. Na príklade grafu veľkých slovenských miest s vzdialenosťami v kilometroch motivuje problém najkratšej cesty. Predstavuje Dijkstrov algoritmus, ktorý počíta najkratšie cesty z jedného vrcholu do všetkých ostatných a vyžaduje nezáporné váhy hrán. Algoritmus si udržiava množinu dokončených vrcholov S, množinu nedokončených vrcholov T a pole dist s doteraz najkratšími nájdenými vzdialenosťami.

• - Tri základné techniky: greedy algoritmy, dynamické programovanie, rozdeľuj a panuj.
• - Pri greedy algoritmoch je najťažšie dokázať správnosť, pri dynamickom programovaní vymyslieť správny podproblém.
• - Graf tvoria vrcholy a hrany, ktoré môžu byť orientované či neorientované a ohodnotené váhami.
• - Graf sa reprezentuje maticou susednosti (test hrany v čase Θ(1)) alebo zoznamami susedov.
• - Problém najkratšej cesty: nájsť najkratšiu cestu z vrcholu U do vrcholu V vo váhovanom grafe.
• - Dijkstrov algoritmus počíta najkratšie cesty z U do všetkých vrcholov a vyžaduje nezáporné váhy hrán.
• - Algoritmus udržiava množiny dokončených (S) a nedokončených (T) vrcholov a pole dist s najkratšími doteraz nájdenými vzdialenosťami.

Zhrnutie pripravené s pomocou AI z prepisu videa.