BFS Shortest Path Coding

EasyPython

Problem

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.

Constraints

1 <= number of locations <= 10^5
0 <= number of edges <= 2 * 10^5
Location names are unique strings
The adjacency lists contain no duplicate edges
start and destination are keys in graph

Function Signature

def shortest_route(graph, start, destination):

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.