 Longest path in a directed acyclic graph

Process vertices in a topological sorting, initializing a fixed source to zero and all other labels to $-\infty$. All possible predecessors have already been processed when a vertex is reached, so maximum-relaxation computes the best path ending there. Induction along the order proves correctness for arbitrary signed weights. Initializing every vertex to zero instead allows a path to start anywhere. Each vertex and edge is processed a constant number of times, giving $O(|V|+|E|)$ running time. For a nonempty-path requirement, maximize the edge-extension candidates rather than including zero as the final answer.