= DAG shortest-path algorithm
{c}
Initialize source distance to zero and other distances to infinity, then process vertices in <topological order>, relaxing their outgoing edges once. Every predecessor on a path to a vertex appears earlier, so induction through that ordering proves that its distance is final when processed. Negative weights are allowed because there are no directed cycles. With <adjacency lists>, <topological sorting> and all <edge relaxations> take $O(|V|+|E|)$ time; predecessor pointers reconstruct paths.
Back to article page
