Data Structures: Weighted Graphs

We all have had the luxury of looking up directions on how to get somewhere on Google Maps, and we usually ignore the intricacies of how such a path is calculated. The idea of Google Maps is based on the concept of graphs, where a giant complex graph is plotted based on nodes (locations) and edges (roadways) to figure out fastest or shortest way to travel. So, if you haven’t thought about this earlier, now certainly you are left wondering how does this elegant navigation feature work. But don’t ponder too much, we are going to cover this concept in this post which is weighted graphs.

a simple weighted graph (weights are the numbers mentioned along the edges)

Note:

If you’re new to the concepts of graphs, be sure to check out my blog series on graphs. Here is the link to my blog on introduction to graphs:

Data Structures: Graph

Basic Terminologies:

Before moving any further let’s take a look at some basic graph terminologies:

1. Vertex: Each node is represented as a vertex of a graph. In the following example the black dots are the vertices of the graph.
2. Edge: Edge is the line which connects two vertices of a graph, it can be thought of as a path from one vertex to another vertex ( more on that later). In the following example the black lines connecting the vertices are the edges of the graph.
3. Adjacency: Two node or vertices are the adjacent if they are connected to each other through an edge.
4. Path: Path is a sequence of vertices connected by edges. It similar to a map in real life the vertices are the locations and the edges are the roads connecting the locations, and there may be various paths from one place to the other. This concept leads to one of the interesting graph processing algorithm on finding the shortest path from one vertex to another.
5. Cycle: A path is said to be a cycle, if the first and last vertices of the path are the same.

a basic undirected graph

So, how does an weighted graph is different from a basic undirected graph?Well weighted graph is a graph whose edges have weights.

The weight of an edge can represent:

1. cost or distance: the amount of effort needed to travel from one place to another
2. capacity: the maximum amount of flow that can be transported from one place to another

a basic weighted graph

Representation:

So, now we’re done with basic terminologies, let’s take look at how weighted graphs are represented. The two most common ways of representing a weighted graph (graph in general) are adjacency matrix and adjacency list.

Adjacency matrix:

To store weighted graph using adjacency matrix form, we call the matrix as cost / weight matrix. Here each cell at position M[i, j] is holding the weight from edge i to j. If the edge is not present, then it wil be infinity. For same node (reflexive property: a node can be thought to be connected to itself), it will be 0.

adjacency matrix representation of weighted graph

Adjacency list:

In the adjacency list, each element in the list will have two values. The first one is the destination node, and the second one is the weight between these two nodes. The representation is like below.

adjacency list representation of weighted graph

So, now we have an idea on what is a weighted graph? With that we will try to build a weighted graph of our own, from scratch. (I will be using Java, as I’m more comfortable with it, but I will be providing the API for it so you could have fun building your own!). The weighted-graph shown below is the one we’re going to implement.

weighted graph which we’re trying to implement via the code shown below

API:

API for the code which is shown below

Code:

Code fore creating and printing a basic weighted graph

That’s it we have successfully built a simple weighted graph from scratch, you could build upon this by adding some more simple features for some graph processing algorithms, like implementing a function which computes the degree of a vertex (number of incoming edges) or find the shortest path between two given vertices.

Applications:

Weighted graphs have a numerous applications, let’s take a look at a few for example.

1. Navigation systems: Let’s take Google Maps for example, this is a graph problem that’s easy to solve with edge-weighted digraphs. Here the weights can be thought of as the distance, traffic and etc., corresponding to the respective locations. The idea is to find the shortest path from one location to another. This can be done with path-finding algorithms like Dijkstra or A* which are based on weighted graph concepts.
2. Minimum spanning trees: MST have direct applications in the design of networks, including computer networks, telecommunications networks, transportation networks and etc. Other practical applications based on minimal spanning trees include — minmax process control, describe financial markets, cluster analysis and etc.

So, we have come to the end of this post and thank you so much 😊 if you have made this far into this post. I will see you in the next post with some weighted-graph processing algorithms!! Always grateful, never complacent!

References:

1. http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/11-Graph/weighted.html
2. https://blogs.cornell.edu/info2040/2011/09/14/google-maps-its-just-one-big-graph/
3. https://algorithms.tutorialhorizon.com/weighted-graph-implementation-java/
4. https://www.tutorialspoint.com/weighted-graph-representation-in-data-structure
5. https://www.javatpoint.com/graph-theory-graph-representations
6. https://www3.cs.stonybrook.edu/~pfodor/courses/CSE260/L29_Weighted_Graphs.pdf
7. https://leapgraph.com/graph-data-structures-applications
8. https://en.wikipedia.org/wiki/Minimum_spanning_tree#:~:text=1.0979027-,Applications,for%2C%20as%20mentioned%20above).

My Github Repository:

1. https://github.com/Sethuram52001/DSA