ADS1: 4. přednáška pro paralelku Y (14.3.2024)
Pavel Veselý
Silná a slabá souvislost orientovaných grafů a hledání komponent silné souvislosti (algoritmus Kosaraju-Sharir) [Pruv 5.9]. Nejkratší cesty v grafech s délkami hran: vlastnosti vzdáleností (trojúhelníková nerovnost) a opakování hledání nejkratších cest z počátečního vrcholu na grafech s jednotkovými délkami hran pomocí BFS. Odvození Dijkstrova algoritmu z BFS pomocí "budíků" pro nezáporné celočíselné délky. Časová složitost za použití pole a haldy pro hledání "budíku", který zazvoní nejdříve [Pruv 6.1 a 6.2].