BFS Shortest Path Coding

BNSF Railway models a simplified network of locations as an unweighted graph. Each edge represents a directly connected route segment, and every segment has equal cost. Given the graph, a starting location, and a destination, return the shortest path as an ordered list of locations.

If the destination cannot be reached, return an empty list. If the start and destination are the same, return a list containing that location.

Formal Specification

Implement shortest_route(graph, start, destination).

• graph is a dictionary mapping each location name to a list of directly connected location names.
• The graph is directed, so an edge from A to B does not imply an edge from B to A.
• start and destination are strings present as keys in graph.
• Return a list of strings containing the shortest path from start to destination, including both endpoints.
• If multiple shortest paths exist, return any one of them.