Djikstra’s algorithm

Have you ever wondered how Google Maps are finding the shortest path to your destination? well, you’re going to know this by the end of this post-reading.

If you’re new to the algorithms let me define what an algorithm is,

Love is an algorithm written between two equal souls

Yes, Love is an algorithm, but it will take a lot of resources, the 🕔time-complexity and space complexity of this algorithm is too high. Ok cool, let’s get into a proper definition for an algorithm.

Algorithm

In mathematics and computer science, an algorithm is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation. To explore more about algorithm see here

Dijkstra’s algorithm

This is the shortest pathfinding algorithm from the source to all other nodes in a directed or undirected graph with non-negative edge weights. This algorithm, published in 1959, is named after its discoverer Edsger Dijkstra, who was a Dutch computer scientist. It is faster than many other ways to do this, but it needs all of the distances connecting the things to be zero or more.

Example of Dijkstra’s algorithm

Consider the following connected and weighted graph, we need to find the shortest path from a given source to all other destinations by using Dijkstra’s algorithm. Here, In the mathematical or in computer terms, the roads are called Edges, and the destinations( S, A, B, C, D) are called Nodes or Vertices.

Here, In the above graph S is the source ( or starting point) from this point, we need to find the shortest path to all other destinations ( A, B, C, D) by using Dijkstra’s algorithm.

Wait I will draw a table to understand this more clear

See the above table, As of now we didn’t visit any places so the distances are unknown to all places( A, B, C, D ) and denoted by infinity (∞). And the distance to S itself is zero( 0 ).In the first step, we’re going to visit A and C from starting point S (Source).

We can see from the above graph we went to the places A and C through the source S. And we can see the distances to A and C through S are 10 and 6.

Like this, we are going to travel to all places and we will update the shortest paths to particular destinations. I think you’re getting how we’re doing this. We are just traveling to all destinations through all possible ways and we will update the shortest path to a particular destination through the S(Source).

In the next step we’re going to travel to other destinations through S->C->… Because as of now S->C is the shortest path i.e 6, to visit other places we will choose this path. We can’t choose S->A… Because it’s a longer distance i.e 10 than S->C.

You can see in the below table we overwritten A. In the previous step we traveled to A with a distance of 10, but now we got the shortest path than the previous one so we updated the shortest one.

Like above we will travel to all destinations in all shortest possible ways and we will update the table by the following graph.

Similarly, we will get the following shortest path table to all destination’s

The following graph is the final, which gives the shortest path to all destinations through the source S.

Conclusion

The Dijkstra’s algorithm is the shortest pathfinding algorithm. We start traveling through the source and we will find the all shortest paths to reach all destinations through S by taking always the shortest path to reach another destination. Yes, this is the Dijkstra’s algorithm and the google maps use this algorithm to give you the shortest path to reach your destination from your source.

If you enjoyed this piece, I’d love it if you hit any comment so others might stumble upon it.

Thank you for giving me your priceless time.