Find the Shortest Path

00:00 Find the Shortest Path. Open the solver module and define the function seen on-screen, which takes a Maze instance and returns the corresponding Solution.

00:46 In this function, you call make_graph() from the converter module to obtain an nx.Graph object, which you then pass to the nx.shortest_path() function.

00:55 Notice how the maze’s .entrance and .exit properties allow you to specify the source and target nodes in the graph. In case NetworkX can’t find the shortest path between them, you handle the exception and return None to indicate that there’s no solution.

01:13 And that’s all you need to solve the maze with NetworkX. You can now test this pathfinding algorithm on your pocket-size maze.

01:55 The solution has six nodes, starting at a square with index eight and ending at a square with index two. When you render the solution, you’ll see this image in your web browser.

02:10 So, that was a fairly simple maze, but what about the giant labyrinth composed of hundreds of squares you saw earlier? Well, it’s easy enough to find out.

02:20 You just load labyrinth.maze and then solve it.

02:33 You can inspect the solution length, squares, which is a considerably longer list than before, and then preview the solution.

02:53 You should see the image that’s seen on-screen. The solution has 121 nodes, which looks impressive. However, there’s a flaw in how you currently compute the shortest path, whose length depends on the number of nodes in the graph instead of the number of squares in each path segment.

03:13 This results in a solution that isn’t the shortest path in terms of actual distance. You’ll address this problem by adding edge weights shortly. But there’s another problem. You are currently unable to distinguish between multiple equivalent solutions.

03:29 What if the maze had several paths with equal lengths? In such a case, you can call nx.all_shortest_paths(), which will return an iterator of the shortest paths in a graph.

03:56 The solve_all() function wraps each yielded path in a Solution instance using a list comprehension.

04:15 It returns an empty list if no solution exists. If you forget about the enemies and rewards for a moment, then the Pac-Man maze that you saw in the beginning of the course has two alternate solutions.

04:31 One goes through the top of the maze, and the other goes through the bottom. However, if you run solve_all() on this maze, you’d still only get one solution.

04:41 Why is this? The problem is that NetworkX calculates the cost of a solution based on the total number of nodes on its path, which may include intersections, corners, and other nodes that don’t actually increase the distance in any way.

04:55 This may sometimes trick the shortest path algorithm into favoring alternative paths with equal distances but fewer nodes. To fix that, you are going to calculate the distance based on the actual number of squares in the maze along the path instead of the number of nodes in the graph.

05:13 To convey the computed distance to NetworkX, you’ll add numeric weights to your graph edges, and you’ll do that in the next section of the course.