= Longest path in a directed acyclic graph
{title2=$L[v]=\max_{(u,v)\in E}(L[u]+w(u,v))$}
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.
Back to article page
