How to Implement a Weighted Graph in Python

One of the most foundational data structures in computer science is the graph. This simple yet flexible construct can be used to model a wide variety of problems, from social network analysis to pathfinding in video games.

These problems often require a bit more sophistication in the form of weighted graphs, where each edge or relation is assigned a numerical value or weight. In this tutorial, we will walk you through how to implement a weighted graph in Python.

Step 1: Define the Node Class

We will first define a Node class that can store the value of the node and a list of its neighbors. This will form the basic building block for our graph.

Step 2: Implement the Weighted Graph

Next, we’ll implement the weighted graph. This will have methods to add nodes, add edges, and find nodes.

Step 3: Testing our Graph

Let’s add nodes and edges to our graph and print out each node and its neighbors to verify whether our program works as expected.

Output:

0: {1: 2, 4: 1}
1: {0: 2, 2: 4}
2: {1: 4, 3: 6}
3: {2: 6, 4: 8}
4: {0: 1, 3: 8, 5: 9}
5: {4: 9}

Step 4: Usage of Weighted Graph

Weighted graphs are widely used in numerous fields such as graph theory, computer science, physics, and lots more. In computer science, it is often associated with algorithms like Dijkstra’s shortest path algorithm, A* search algorithm etc for finding the shortest path in a weighted graph.

Full Code:

Output:

0: {1: 2, 4: 1}
1: {0: 2, 2: 4}
2: {1: 4, 3: 6}
3: {2: 6, 4: 8}
4: {0: 1, 3: 8, 5: 9}
5: {4: 9}

Conclusion

In this tutorial, we have implemented a weighted graph using Python. You should now understand how to define nodes, create a graph, and add nodes and edges with relative weights to them. This provides a good starting point for more advanced graph-based problems like shortest path and minimum spanning tree algorithms.