# 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.

Become a Member to join the conversation.