Add Weights to Graph Edges

00:00 Add Weights to Graph Edges. Go back to the converter module and update the Edge class by adding a property that will calculate the actual distance between its two nodes.

00:13 Here, you want to calculate the Euclidean distance between the nodes using Python’s math module, so it’s imported first.

00:31 The math.dist() function takes two points specified as sequences of coordinates. In this case, you provide tuples of the row and column indices of squares corresponding to the nodes. Note that you could define distance differently—for example, as the sum of absolute values of differences in the horizontal and vertical directions. You can update the function make_graph() to use the new property.

01:06 Notice how you change the graph data passed to nx.Graph, which is now a sequence of tuples consisting of the two nodes and a dictionary with extra attributes.

01:16 You specify only one attribute named weight, whose value is equal to the edge’s distance. Next, update the functions in the solver module to tell NetworkX which attribute to use as the weight.

01:38 The weight parameter lets you specify the name of an attribute in a dictionary associated with each graph edge.

01:54 Now, when you call solve_all() on the Pac-Man maze, you’ll get two equivalent solutions, which lead you to the exit on the left. Clearly, both paths have the same length, so it shouldn’t matter which one you choose. However, notice that the upper path contains three extra nodes representing the intersections, including one with a chamber opening in the middle of the maze, while the lower path doesn’t.

02:19 Now you have weights in your graph, you can use other factors besides the distance to influence the algorithm’s decision. For example, you may want to favor paths with fewer enemies or more rewards, and you’ll find out how to do that in the next section of the course.