 DAG shortest-path algorithm

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.