= Maximum-product edge-labelled walk
{title2=$P_t(v)=\max P_{t-1}(u)p(u,v)$}
Attach nonnegative <edge> scores to <edge-labelled walk matching>. For each layer and endpoint, keep the greatest product over matching prefixes. Only <edges> with the required current label enter the maximum. Multiplication by a nonnegative score preserves order, proving the <dynamic programming> recurrence. Store a predecessor for each reachable layer entry to recover a maximizing walk. A reachable score of zero must be distinguished from no matching walk: keep reachability separately or use an impossible negative sentinel and skip it before multiplication. The score is the defined product; interpreting it as a physical event <probability> can require extra independence assumptions.
Back to article page
