The following piece of code reproduces the steps we followed in the previous section.
Given a graph, G, the shortest_path function will iterate over the graph to find the shortest path between the start and end nodes.
Each iteration, starting at step_start_node, will do the following:
- Find the neighbors of step_start_node.
- For each neighbor, n (skip n if it has already been visited) do the following:
- Compute the distance between n and step_start_node using the weight associated with the edge between n and step_start_node.
- If the new distance is shorter than the previously saved one (if any), save the distance and the incoming (parent) node into the shortest_distances dictionary.
- Add step_start_node to the list of visited nodes.
- Update step_start_node for the next iteration:
- The next iteration will start from the node closest to start_node that has not yet been visited.
- Repeat until end_node is marked...
