Walking the Approximate Longest Path