Fewest Stops on the Metro

A metro map is a list tracks of pairs [a, b]: trains run between the neighbouring stations a and b in both directions. Write fewest_stops(tracks, start, goal) that returns the route from start to goal that passes through the fewest stations, as a list of station names that begins with start and ends with goal.

Often several routes are equally short. Then return the one that comes first alphabetically when you compare the routes station by station, which is how Python compares two lists. If goal cannot be reached, return []. If start and goal are the same station, the route is [start].

Examples

tracks = [['ash', 'elm'], ['oak', 'ash'], ['elm', 'fir'], ['oak', 'fir'], ['fir', 'yew']]
fewest_stops(tracks, 'ash', 'yew')  # returns ['ash', 'elm', 'fir', 'yew']
fewest_stops(tracks, 'yew', 'ash')  # returns ['yew', 'fir', 'elm', 'ash']
fewest_stops([['ash', 'elm']], 'ash', 'oak')  # returns []

From ash, the routes through elm and through oak both reach yew in four stations. They first differ at the second station, and 'elm' comes before 'oak', so the route through elm wins.

Constraints

• Up to 2,000 stations and 5,000 tracks. A track can be listed more than once, in either order.
• Station names are lowercase strings.