Solve the Maze Using a Graph-Based Approach

00:00 Solve the Maze Using a Graph-Based Approach. At this point, you can represent the maze and its solution in an object-oriented form. You can visualize them, as well as serialize the maze using a custom binary file format.

00:15 Now it’s time to convert your maze to a graph and let Python find the shortest path from the entrance to the exit. By the end of this part of the course, you’ll have a command-line program for solving and visualizing mazes loaded from a specified file.

00:32 Graphs are an important data structure in theoretical computer science, which often come up during code interviews. While you may use them sparingly in your day-to-day programming practice, graphs can help solve a variety of problems, such as finding your way out of a maze.

00:50 A graph is a set of nodes and the edges between them. Because nodes have no inherent location in space, when you convert the maze into a graph form, you will lose some information about its geometry. Later, you’ll add weights to the edges to represent the cost of traversing each connection between two nodes.

01:10 Rather than reinventing the wheel, you’ll use a graph representation provided by the popular NetworkX library, which ships with a couple of useful graph algorithms.

01:23 The first step is to add this library to your pyproject.toml file by listing it as the project’s dependency.

01:34 As a rule of thumb, you should avoid specifying concrete dependency versions directly in the pyproject.toml file, particularly when you intend to use your package as a reusable library in other projects that might depend on different NetworkX versions.

01:51 However, it’s always a good idea to pin dependency versions in a requirements.txt file to ensure reproducible builds. Next, reinstall your package in your virtual environment using the editable mode once more so that the networkx package becomes available for importing.

02:17 You can also create a requirements file pinning specific dependencies.

02:30 Before moving on, you create your final Python package in your project with the converter and solver placeholder modules. The converter module will contain a few functions for turning your maze into a graph, while the solver module will use those functions as glue code to wrap NetworkX’s algorithms and solve your maze.

02:51 So, with the foundations created, in the next section of the course, you’ll start writing the converter module to transform the maze into a graph.