Skip to Content
Learn
Graphs: Python
Finding a Path II

Our pathfinding method is almost complete. Let’s take a step back and think how a passenger in Harwick station could find their way to Callan.

First, they’d look for all the stations connected to Harwick. If one of those stations was Callan, they’re in luck!

Otherwise, they would look for the connections from each of those stations excluding Harwick because they’ve already crossed it off their list.

We’ll take the same strategy with our pathfinding method.

while len(start) > 0: current_vertex = start.pop(0) # current_vertex is end_vertex # a path exists! # current_vertex is not end_vertex # add vertices connected to # current_vertex onto the list # to keep searching for a path

Instructions

1.

Tab over graph.py. In the while loop of the .find_path() method, check current_vertex against the given argument end_vertex.

If current_vertex matches the end_vertex argument, then you’ve found a path and can return True .

Tab over to script.py and run the code.

2.

Otherwise current_vertex doesn’t match, and we need to keep looking.

Make a new variable vertex and assign it to the vertex instance by using current_vertex to key into self.graph_dict.

3.

Call .get_edges() on vertex. Assign the result to a variable called next_vertices.

4.

Add the next_vertices list to the end of start.

If the while loop concludes and we’ve never returned True, then we know the current_vertex never matched end_vertex. There is no path!

Return False after the while loop has concluded.

Go to script.py. Uncomment and run the code.

Folder Icon

Sign up to start coding

Already have an account?