Data Structures and Algorithms: Weighted Graph Processing — Part 1: Dijkstra

Sethuram.S.V

6 min readFeb 9, 2021

--

Last time around, we saw about what is a weighted graph? How to build one from scratch? Where can it be used? In case, if you need a small recap on weighted-graph or if you’re new to weighted-graph, check out my previous post:

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…

sethuram52001.medium.com

This time around, we’ll look at some of the weighted-graph processing algorithms. To be specific we’ll discuss about Dijkstra and A*. Both are similar algorithms used to find paths in a weighted graph. A* is basically based on the same idea as Dijkstra, but with a little twist to it. So without any further ado, let’s jump into the intricate, intimidating, yet fun world of algorithms.

Dijkstra

Dijkstra’s algorithm seeks to find the shortest path between two nodes in a weighted graph. Let’s take an example of a road network as graph and weights on the edge may represent the traffic, speed limit and any other factors which limits the travelling.

As shown in the map, you’re starting point and destination are the blocks in yellow colour, named start and end respectively. As you can see for yourself the possible routes to traverse have a numeric along it which is the weight of the edge. For this graph, you may be able to find out the optimal path by trial and error method as it’s a sparse graph. But what about a dense graph, like the one below:

That’s where the algorithms come along for the ride, so let’s take a look at Dijkstra’s.

Before jumping into the algorithm, let’s try to get some basic intuition what Dijkstra’s algorithm, hoping to accomplish and the approach it takes for the same.

Note on Edge Relaxation

Edge relaxation is a important concept in algorithms regarding ‘shortest paths calculation’ like Dijkstra’s or Bellman-Ford algorithm. To make it concise you can edge relaxation is nothing but:

if(d[u] + c(u,v) < d[v])
   d[v] = d[u] + c(u,v)

where, c(u,v) represents the cost/weight along the edge from vertex u to v. d[x] is the current least cost/distance to vertex x. Here is an example:

a simple weighted graph: before and after relaxation

Basic Idea of Dijkstra’s algorithm

Dijkstra’s algorithm with the start node given to it, it starts analysing the graph to find the shortest path between the start node and all the other nodes in the graph. On the process of it, it keeps track of the currently known nodes with shortest distance from source node to other nodes. Once it visits a node it marks the node as visited. Then it goes onto look out for the next unvisited node while computing for the shortest path, this process continues until a path that connects the source node to all other nodes following the shortest path possible to reach each node.

Algorithm

Let the node at which we are starting be called the start node.

Mark all the nodes as unvisited. Create a set of all the unvisited nodes called the unvisited set.
Assign to every node a tentative distance value: set it to zero our initial node and to infinity for all other nodes. Set the initial node as current.
Relaxation: For the current node, consider all of its unvisited neighbours and calculate their tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbour B has length 2, then the distance to B through A will be 6+2=8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, the current value will be kept.
When we are done considering all of the unvisited neighbours of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.
Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new “current node”, and go back to step 3.

That’s a lot of words to be honest 😅, so why don’t we take a look at the illustration below to get a better understanding of the algorithm, while doing so try to correlate with the algorithm:

Note

I have given the code in java, as I’m more comfortable with java, but I have given the API down below, so you could try out code it in the language whichever you’re most comfortable in.

API

Code

We’re going to try to implement Dijkstra’s for the weighted graph, given below:

We’re using an adjacency matrix to represent the graph, where the matrix has a positive entry if there’s a edge running between the two nodes(row and col), the value of graph[i][j] is the weight along the vertices i and j.

Drawback of Dijkstra’s algorithm

Dijkstra’s algorithm doesn’t work as it’s intended to when it comes to graphs with negative weighted edges. This is because, once a node is marked as “visited”, the current path to that node is marked as the shortest path to reach that node. And negative weights can alter this if the total weight can be decremented after this step has occurred. Let’s take an example to get a better understanding:

The output from the code which we saw for Dijkstra’s algorithm is shown below:

As you could have noticed by now, Dijkstra’s algorithm is a greedy approach, which doesn’t guarantee optimal solution though it gives an approximate solution in reasonable time. As the result of that once the edge is relaxed Dijkstra’s algo doesn’t look for that vertex once more. As you can see if you break down an optimal solution: the vertex 2 must have -3 when you traverse through 1 -> 4 -> 3 -> 2 but it doesn’t, which is the drawback of Dijkstra’s algorithm.

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, which is the continuation of this post where we’ll see about A*. Always grateful, never complacent!

References

My Github Repository

https://github.com/Sethuram52001/DSA