Acyklické orientované grafy nám už z definice zaručují, že nebudou obsahovat záporný cyklus. Neobsahují totiž žádný cyklus. Proto v nich najdeme nejkratší cestu následujícím jednoduchým způsobem:

  1. Nalezneme topologické uspořádání.
  2. Procházíme vrcholy v nalezeném pořadí a updatujeme hrany z nich vedoucí.

První fázi vyřešíme pomocí průchodu do hloubky. Druhou jednoduchým průchodem vrcholů. Tím pádem zvládneme obě fáze v čase $\OO(n+m)$ a celý algoritmus poběží v lineárním čase. Připomeňme, že hrany mohou být ohodnoceny libovolně. Tedy i zápornými čísly.

O Dijkstrově algoritmu se dá říci, že funguje podobně jako hledání nejkratší cesty v acyklických orientovaných grafech, akorát uspořádání vrcholů podle nejkratší cesty hledáme za chodu.

Poznamenejme ještě, že v acyklických orientovaných grafech můžeme podobným způsobem hledat i nejdelší cestu. Takovému algoritmu se říká algoritmus kritické cesty. Byl pojmenován kvůli následující aplikaci. Acyklický orientovaný graf popisuje závislosti mezi činnostmi projektu. Hrany odpovídají činnostem a ohodnocení hran době, jak dlouho bude daná činnost probíhat. Doba potřebná k dokončení projektu je délka nejdelší cesty. Nejdelší cestě se říká kritická, protože každé zpoždění činností na kritické cestě způsobí zpoždění celého projektu.

Příklad: Na následujícím ohodnoceném grafu $G=(V,E)$ najděte nejkratší cestu z $A$ do všech ostatních vrcholů.

Délky nejkratších cest z $A$ do $A$, $B$, $C$, $D$, $E$ jsou $0$, $2$, $3$, $4$, $6$. Na papíře můžeme vzdálenosti počítat rovnou. Procházíme vrcholy zleva doprava (v topologickém pořadí) a pro každý vrchol $v$ spočítáme podle hran do něj vedoucích jeho $\ARRAY{d}{v} := \min\{ \ARRAY{d}{w}+c(wv)\,|\, wv\in E \}$.