Metoda kritické cesty: Porovnání verzí

m
linkfix
m (linkfix)
<!-- bylo by nejlepší udělat animák, kdo ho udělá? :) -->
[[Soubor:Critical path algorithm.svg|Příklad grafu - červeně je vyznačena kritická cesta ABDGH.|thumb|right|300px]]
Sestrojíme [[orientovaný graf|orientovaný]], [[ohodnocený graf|ohodnocený]] graf reprezentující projekt. Každá hrana v něm má svoji váhu a každý vrchol své označení + dvě prázdné proměnné (levá a pravá) pro zápis hodnot [[cesta (grafygraf)|cest]]. Hrany, které budou ležet na cestách, si budeme označovat. Graf může obsahovat i více než jednu kritickou cestu.
 
Nejprve projdeme graf zleva ze vstupního vrcholu (hodnota jeho levé proměnné je na začátku 0). Do levé proměnné tohoto vrcholu pak zapíšeme hodnotu cesty (hodnota cesty z předchozího vrcholu + hodnota hrany). Hranu vybíráme tak, že při vstupu do nějakého vrcholu budeme vybírat vždy hranu, ze které dostaneme nejvyšší hodnotu cesty (např. do vrcholu D půjdeme po hraně z B, protože cesta má hodnotu 7, což je vyšší než z C, kde má cesta hodnotu 4).