= 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.
Back to article page
