This lesson's interactive features are locked, please to keep using them
Dijkstra's: Get Path
Testing of the Mappy app revealed that both breadth-first search (BFS) and depth-first search (DFS) were too slow for finding optimal routes.
Let's build a faster solution using Dijkstra's algorithm!
Assignment
First, we'll need a helper function that will be essential later. The get_path(dest: str, predecessors: dict[str, str]) -> list[str] function has two inputs:
dest: A string representing the label of the destination node.predecessors: A dictionary ofnode: node, where each node is mapped to its "predecessor" in the path. For example,"Vegas": "Philadelphia"indicates that Philadelphia leads to Vegas in our path.
This function returns a list of nodes representing the path that was taken through the graph by following the predecessors.
Complete the get_path Function
Starting at the dest node, traverse the predecessors dictionary backwards, building the final path as you go.
For example, given:
dest="York"predecessors={"York": "London", "Hampshire": "Manchester", "London": "Hampshire"}
The final path would be: ["Manchester", "Hampshire", "London", "York"]