Find the Shortest Path
Notice how the maze’s
.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.
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.
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: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.
Become a Member to join the conversation.