Web Crawler Shortest Path Reconstruction

A crawler has a complete, finite snapshot of the outgoing links between the distinct page names in pages. Each row [from, to] in links is a directed link. Following one link costs one click.

Return a shortest path from start to target as an array of page names, including both endpoints. Minimize the number of links used. If several paths use that minimum number, return the lexicographically smallest sequence of page names: compare the first unequal names using ordinary lowercase string order, with a proper prefix smaller than its extension.

• If start == target, return [start], even when that page has no links.
• If the target cannot be reached, return an empty array.
• Links are directed; do not add reverse links. Cycles and self-links are allowed.
• The order of pages and input link rows does not determine the answer.

The snapshot represents successful calls to a link-discovery API: a page's outgoing links are exactly the rows whose first entry names that page. There are no network calls, failures or retries in the judged input.

Address the space follow-up by storing one predecessor per discovered page and reconstructing the answer afterward, rather than carrying a separate full path with each queued page.