Longest path

A longest path maximizes path length, either the number of edges or the sum of specified edge weights, under the stated endpoints and simple-path convention. In a general graph, imposing vertex simplicity makes the optimization computationally difficult; a Directed acyclic graph admits a direct dynamic programming solution. Allowing arbitrary walks instead requires care with reachable positive cycles. The convention permitting a zero-edge path gives a possible value zero even when all nonempty paths have negative weight.

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.