• Category
  • >Machine Learning

Dijkstra’s Algorithm: The Shortest Path Algorithm

  • Neelam Tyagi
  • Dec 14, 2020
  • Updated on: Jul 19, 2022
Dijkstra’s Algorithm: The Shortest Path Algorithm title banner

A Dutch computer scientist, Edsger Dijkstra, in 1959, proposed an algorithm that can be applied to a weighted graph. The graph can either be directed or undirected with the condition that the graph needs to embrace a non-negative value on its every edge. He named this algorithm “Dijkstra’s Algorithm” at his name. 

 

Let’s dive right into the blog and we will learn 

 

  1. Introduction to Graphs

  1. What is Dijkstra’s Algorithm?

  2. How to Implement the Dijkstra's Algorithm?

  3. Working Example of Dijkstra's Algorithm

  4. Applications of Dijkstra’s Algorithm

  5. Advantages and Disadvantages of Dijkstra’s Algorithm

 

In the series of blogs, we particularly focus on the detailed study, based on graphs, i.e., Group Theory and knowledge Graph, this blog will serve in building our knowledge base to the next level.


 

Introduction to Graphs

 

In simple words, graphs are data structures that are used to depict connections amidst a couple of elements where these elements are called nodes (or vertex) that generally real-time objects, persons or entities and connections amid nodes are termed as edges. Also, two nodes only get connected if there is an edge between them.

 

"A graph is essentially an interrelationship of nodes/vertices connected by edges."

 

Generally, graphs are suited to real-world applications, such as graphs can be used to illustrate a transportation system/network, where nodes represent facilities that transfer or obtain products and edges show routes or subways that connect nodes. 

 

Graphs can be divided into two parts;

 

  • Undirected Graphs: For every couple of associated nodes, if an individual could move from one node to another in both directions, then the graph is termed as an undirected graph.

 

  • Directed Graphs: For every couple of associated graphs, if an individual could move from one node to another in a specific (single) direction, then the graph is known as the directed graph. In this case, arrows are implemented rather than simple lines in order to represent directed edges.

 

Weighted Graphs

 

The weight graphs are the graphs where edges of the graph have “a weight” or “cost” and also where weight could reflect distance, time, money or anything that displays the “association” amid a couple of nodes it links. These weights are an essential element under Dijkstra's Algorithm. 


 

What is Dijkstra’s Algorithm?

 

What if you are provided with a graph of nodes where every node is linked to several other nodes with varying distance. Now, if you begin from one of the nodes in the graph, what is the shortest path to every other node in the graph? 

 

Well simply explained, an algorithm that is used for finding the shortest distance, or path, from starting node to target node in a weighted graph is known as Dijkstra’s Algorithm.

 

This algorithm makes a tree of the shortest path from the starting node, the source, to all other nodes (points) in the graph.

 

Dijkstra's algorithm makes use of weights of the edges for finding the path that minimizes the total distance (weight) among the source node and all other nodes. This algorithm is also known as the single-source shortest path algorithm.

 

Also Read | Branches of Discrete Mathematics

 

Dijkstra’s algorithm is the iterative algorithmic process to provide us with the shortest path from one specific starting node to all other nodes of a graph. It is different from the minimum spanning tree as the shortest distance among two vertices might not involve all the vertices of the graph.

 

It is important to note that Dijkstra’s algorithm is only applicable when all weights are positive because, during the execution, the weights of the edges are added to find the shortest path.

 

And therefore if any of the weights are introduced to be negative on the edges of the graph, the algorithm would never work properly. However, some algorithms like the Bellman-Ford Algorithm can be used in such cases.

 

It is also a known fact that breadth-first search(BFS) could be used for calculating the shortest path for an unweighted graph, or for a weighted graph that has the same cost at all its edges.

 

But if the weighted graph has unequal costs at all its edges, then BFS infers uniform-cost search. Now what?

 

Instead of extending nodes in order of their depth from the root, uniform-cost search develops the nodes in order of their costs from the root. And a variant of this algorithm is accepted as Dijkstra’s Algorithm.  

 

Generally, Dijkstra’s algorithm works on the principle of relaxation where an approximation of the accurate distance is steadily displaced by more suitable values until the shortest distance is achieved.

 

Also, the estimated distance to every node is always an overvalue of the true distance and is generally substituted by the least of its previous value with the distance of a recently determined path.

 

It uses a priority queue to greedily choose the nearest node that has not been visited yet and executes the relaxation process on all of its edges. (From)

 

Example Involved

 

For example, an individual wants to calculate the shortest distance between the source, A, and the destination, D, while calculating a subpath which is also the shortest path between its source and destination. Let’s see here how Dijkstra’s algorithm works;

 

It works on the fact that any subpath, let say a subpath B to D of the shortest path between vertices A and D is also the shortest path between vertices B and D, i.e., each subpath is the shortest path.

 

Here, Dijkstra’s algorithm uses this property in the reverse direction, that means, while determining distance, we overestimate the distance of each vertex from the starting vertex then inspect each node and its neighbours for detecting the shortest subpath to those neighbours. 

 

This way the algorithm deploys a greedy approach by searching for the next plausible solution and expects that the end result would be the appropriate solution for the entire problem.


 

How to Implement the Dijkstra Algorithm?

 

Before proceeding the step by step process for implementing the algorithm, let us consider some essential characteristics of Dijkstra’s algorithm;

 

  • Basically, the Dijkstra’s algorithm begins from the node to be selected, the source node, and it examines the entire graph to determine the shortest path among that node and all the other nodes in the graph. 

  • The algorithm maintains the track of the currently recognized shortest distance from each node to the source code and updates these values if it identifies another shortest path.

  • Once the algorithm has determined the shortest path amid the source code to another node, the node is marked as “visited” and can be added to the path.

  • This process is being continued till all the nodes in the graph have been added to the path, as this way, a path gets created that connects the source node to all the other nodes following the plausible shortest path to reach each node.

 

Also Read | Types of Statistical Analysis

 

Now explaining the step by step process of algorithm implementation;

 

  1. The very first step is to mark all nodes as unvisited,

  2. Mark the picked starting node with a current distance of 0 and the rest nodes with infinity, 

  3. Now, fix the starting node as the current node,

  4. For the current node, analyse all of its unvisited neighbours and measure their distances by adding the current distance of the current node to the weight of the edge that connects the neighbour node and current node,

  5. Compare the recently measured distance with the current distance assigned to the neighbouring node and make it as the new current distance of the neighbouring node,

  6. After that, consider all of the unvisited neighbours of the current node, mark the current node as visited,

  7. If the destination node has been marked visited then stop, an algorithm has ended, and

  8. Else, choose the unvisited node that is marked with the least distance, fix it as the new current node, and repeat the process again from step 4. 

 

 

Working Example of Dijkstra's Algorithm

 

In the above section, you have gained the step by step process of Dijkstra’s algorithm, now let’s study the algorithm with an explained example.

 

We will calculate the shortest path between node C and the other nodes in the graph.


Displaying the example of the Dijkstra's algorithm

Example of Dijkstra's Algorithm


  1. During the execution of the algorithm, each node will be marked with its minimum distance to node C as we have selected node C. 

 

In this case, the minimum distance is 0 for node C. Also, for the rest of the nodes, as we don’t know this distance, they will be marked as infinity (∞), except node C (currently marked as red dot).


Displaying the Node C as current node

Graphical Representation of Node C as Current Node


  1. Now the neighbours of node C will be checked, i.e, node A, B, and D. We start with B, here we will add the minimum distance of current node (0) with the weight of the edge (7) that linked the node C to node B and get 0+ 7= 7.

 

Now, this value will be compared with the minimum distance of B (infinity), the least value is the one that remains the minimum distance of B, like in this case, 7 is less than infinity, and marks the least value to node B.


Assigning Node B a minimum distance value.

Assign Node B a minimum distance value


  1. Now, the same process is checked with neighbour A. We add 0 with 1 (weight of edge that connects node C to A), and get 1. Again, 1 is compared with the minimum distance of A (infinity), and marks the lowest value.


     

Assigning Node A a minimum distance value.

Assign Node A a minimum distance value


The same is repeated with node D, and marked 2 as lowest value at D.


Assign Node D a minimum distance value

Assign Node D a minimum distance value


Since, all the neighbours of node C have checked, so node C is marked as visited with a green check mark.


 

Displaying the image where node C is marked as visited with green mark.

Marked Node C as visited 


  1. Now, we will select the new current node such that the node must be unvisited with the lowest minimum distance, or the node with the least number and no check mark. Here, node A is the unvisited with minimum distance 1, marked as current node with red dot. 


Graphical Representation of Node A as Current Node

Graphical Representation of Node A as Current Node


We repeat the algorithm, checking the neighbour of the current node while ignoring the visited node, so only node B will be checked.

 

For node B, we add 1 with 3 (weight of the edge connecting node A to B) and obtain 4. This value, 4, will be compared with the minimum distance of B, 7, and mark the lowest value at B as 4. 


Assign Node B a minimum distance value

Assign Node B a minimum distance value


  1. After this, node A marked as visited with a green check mark. The current node is selected as node D, it is unvisited and has a smallest recent distance. We repeat the algorithm and check for node B and E.


 

Graphical Representation of Node D as Current Node

Graphical Representation of Node D as Current Node


For node B, we add 2 to 5, get 7 and compare it with the minimum distance value of B, since 7>4, so leave the smallest distance value at node B as 4. 

 

For node E, we obtain 2+ 7= 9, and compare it with the minimum distance of E which is infinity, and mark the smallest value as node E as 9. The node D is marked as visited with a green check mark.


Marked Node D as visited

Marked Node D as visited


  1. The current node is set as node B, here we need to check only node E as it is unvisited and the node D is visited. We obtain 4+ 1=5, compare it with the minimum distance of the node.

 

As 9 > 5, leave the smallest value at node node E as 5. 

 

We mark D as visited node with a green check mark, and node E is set as the current node.


Depicting Node B as visited with green check mark.

Marked Node B as visited


  1. Since it doesn’t have any unvisited neighbours, so there is not any requirement to check anything. Node E is marked as a visited node with a green mark.


The image is showing the all nodes are marked as visited with green check mark.

Marked Node E as visited


So, we are done as no unvisited node is left. The minimum distance of each node is now representing the minimum distance of that node from node C.

 

Also Read | What is the Confusion Matrix

 

Applications of Dijkstra’s Algorithm

 

Before learning any algorithm, we should know the fundamental purpose of using an algorithm that could help us in real-world applications. Such as, for Dijkstra’s algorithm, we are trying to find the solutions to least path based problems. 

 

For example, if a person wants to travel from city A to city B where both cities are connected with various routes. Which route commonly he/ she should choose?

 

Undoubtedly, we would adopt the route through which we could reach the destination with the least possible time, distance and even cost. 

 

Further, with the discussion, it has various real-world use cases, some of the applications are the following:

 

  • For map applications, it is hugely deployed in measuring the least possible distance and check direction amidst two geographical regions like Google Maps, discovering map locations pointing to the vertices of a graph, calculating traffic and delay-timing, etc.

  • For telephone networks, this is also extensively implemented in the conducting of data in networking and telecommunication domains for decreasing the obstacle taken place for transmission.

  • Wherever addressing the need for shortest path explications either in the domain of robotics, transport, embedded systems, laboratory or production plants, etc, this algorithm is applied.

  • Besides that, other applications are road conditions, road closures and construction, and IP routing to detect Open Shortest Path First.


 

Advantages and Disadvantages of Dijkstra’s Algorithm

 

Discussing some advantages of Dijkstra’s algorithm; 

 

  1. One of the main advantages of it is its little complexity which is almost linear. 

  2. It can be used to calculate the shortest path between a single node to all other nodes and a single source node to a single destination node by stopping the algorithm once the shortest distance is achieved for the destination node.

  3. It only works for directed-, weighted graphs and all edges should have non-negative values.

 

Despite various applications and advantages, Dijkstra’s algorithm has disadvantages also, such as;

 

  1. It does an obscured exploration that consumes a lot of time while processing,

  2. It is unable to handle negative edges,

  3. As it heads to the acyclic graph, so can’t achieve the accurate shortest path, and

  4. Also, there is a need to maintain tracking of vertices, have been visited.

 

Also Read | What is Conditional Probability

 

 

Conclusion

 

Among many, we have discussed the Dijkstra algorithm used for finding the shortest path, however, one of the obstacles while implementing the algorithm on the internet is to provide a full representation of the graph to execute the algorithm as an individual router has a complete outline for all the routers on the internet. We have seen

 

  • Graphs are used to display connections between objects, entities or people, they have the main elements: Nodes and edges.

  • Dijkstra’s algorithm enables determining the shortest path amid one selected node and each other node in a graph.

  • And finally, the steps involved in deploying Dijkstra’s algorithm.

 

Also Read | Statistical Data Analysis

 

I hope you really enjoyed reading this blog and found it useful, for other similar blogs and continuous learning follow us regularly. 

Latest Comments

  • cindybyrd547

    Nov 15, 2022

    Get Your Ex Back and this is relatively easier than what you think. My name is Cindy Byrd from USA. My boyfriend that left me a few months ago just came back to me last night crying for me to take him back. My boyfriend left me and I was devastated. The most painful thing is that I was pregnant for him. I wanted him back. I did everything within my reach to bring him back but all was in vain, I wanted him back so badly because of the love I had for him, I begged him with everything, I made promises but he refused. I explained my problem to my sister and she suggested that I should rather contact a spell caster that could help me cast a spell to bring him back , I had no choice than to try it. I messaged the spell caster called Dr.Excellent, and he assured me there was no problem and that everything will be okay before 28hours. He cast the spell and surprisingly 28 hours later my boyfriend called me. It was so surprising, I answered the call and all he said was that he was so sorry for everything that had happened He wanted us to come back together. He also said he loved me so much. I was so happy and went to him that was how we started living together happily again.thanks to Dr.Excellent . if you are here and your Lover is turning you down, or your boyfriend moved to another girl, do not cry anymore, contact Dr.Excellent for help now.. Here his contact. WhatsApp: +2348084273514 , Email: Excellentspellcaster@gmail.com His website:https://drexcellentspellcaster.godaddysites.com/

  • Juliana Davis

    Nov 16, 2022

    i want to share to the whole world how Dr Kachi the Great of all the Spell Caster, that helped me reunite my marriage back, my Ex Husband broke up with me 3months ago, I have been trying to get him back ever since then, i was worried and so confused because i love him so much. I was really going too much depressed, he left me with my kids and just ignored me constantly. I have begged him for forgiveness through text messages for him to come back home and the kids crying and miss their dad but he wont reply, I wanted him back desperately. we were in a very good couple and yet he just ignores me and get on with his life just like that, so i was looking for help after reading a post of Dr Kachi on the internet when i saw a lady name SHARRON testified that Dr Kachi cast a Pure love spell to stop divorce. and i also met with other, it was about how he brought back her Ex lover in less than 24 hours at the end of her testimony she dropped his email, I contacted Dr Kachi via email and explained my problem to Dr Kachi and he told me what went wrong with my husband and how it happen, that he will restored my marriage back, and to my greatest surprise my Ex husband came back to me, and he apologized for his mistake, and for the pain he caused me and my children. Then from that day our marriage is now stronger than how it was before, Dr Kachi you're a real spell caster, you can also get your Ex back and live with him happily: Contact Email drkachispellcast@gmail.com his Number CALL/ WHATSAPP: +1 (209) 893-8075 Visit his Website: https://drkachispellcast.wixsite.com/my-site

  • Josh

    Nov 16, 2022

    All thank to Dr Ayoola, My name is Josh Buster I live in California, I want to let the world know how this man changed my life and that of my family. I have been playing jackpot for so many years now hoping to win and start my own business, I have been a driver and same time I have being playing lottery game for more than 10 years now each time I play I always run out of luck. one day I was browsing with my phone when I saw some testimonies about this man call Dr Ayoola on how he has helped people win lottery games, I was shook and I ask myself if this is true and also contacted this man for help and told him everything, why I contacted him. He asked me if I have been playing lottery game before now and I said yes. He told me that he will help me with the right number to win if only we work together which I told him I am ready to work with him. After working with him he gave me a number to play, after playing the number Dr Ayoola gave to me, I came out a winner of jackpot of 1,000,000 millions dollars all thanks to you Dr Ayoola for your help I am so happy now. And now I am fulfilling my promise by sharing your good work to the world. Dr Ayoola is a great man and a man GOD has sent to help people and put a smile on peoples face. Thank you for what you have done for me Dr Ayoola I will be for ever grateful to you, you can contact him if you are willing to change your story for good via drayoolasolutionhome@gmail.com or https://www.facebook.com/Dr-Ayoola-105640401516053/ text or call +14809032128

  • cindybyrd547

    Nov 18, 2022

    Get your ex back fast and this is relatively easier than what you think. My name is Cindy Byrd from USA. My boyfriend that left me a few months ago just came back to me last night crying for me to take him back. My boyfriend left me and I was devastated. The most painful thing is that I was pregnant for him. I wanted him back. I did everything within my reach to bring him back but all was in vain, I wanted him back so badly because of the love I had for him, I begged him with everything, I made promises but he refused. I explained my problem to my sister and she suggested that I should rather contact a spell caster that could help me cast a spell to bring him back , I had no choice than to try it. I messaged the spell caster called Dr.Excellent, and he assured me there was no problem and that everything will be okay before 28hours. He cast the spell and surprisingly 28 hours later my boyfriend called me. It was so surprising, I answered the call and all he said was that he was so sorry for everything that had happened He wanted us to come back together. He also said he loved me so much. I was so happy and went to him that was how we started living together happily again.thanks to Dr.Excellent . if you are here and your Lover is turning you down, or your boyfriend moved to another girl, do not cry anymore, contact Dr.Excellent for help now.. Here his contact. WhatsApp: +2348084273514 , Email: Excellentspellcaster@gmail.com His website:https://drexcellentspellcaster.godaddysites.com/

  • Natasha Thompson

    Nov 18, 2022

    My name is Natasha Thompson from the USA/Texas.. Am so overwhelmed with gratitude to let the world know how Dr Kachi, the great spell caster changed my life for good. It all started when I lost my job and I was down financially and emotionally because I couldn’t be able provide for my two kids and staying home all day Jobless it’s not easy until I was checking on the internet when I saw a series of testimonies hearing people winning the Powerball lottery, I didn’t believed, but being poor no job you have no option. I gave it a try and I contacted Dr Kachi who told me what i have to do before I can become a big lottery winner and I accepted. He made special prayers for me in his temple and gave me the required numbers to play the lottery game and when I used the numbers to play it, I won a massive $344.6 million Powerball jackpot. I was so happy and I choose to review my winning in any platform, I would love other people to seek help from Dr Kachi through WhatsApp/number and Call: +1 (209) 893-8075 or email drkachispellcast@gmail.com by his website: https://drkachispellcast.wixsite.com/my-site

  • Natasha Thompson

    Nov 18, 2022

    My name is Natasha Thompson from the USA/Texas.. Am so overwhelmed with gratitude to let the world know how Dr Kachi, the great spell caster changed my life for good. It all started when I lost my job and I was down financially and emotionally because I couldn’t be able provide for my two kids and staying home all day Jobless it’s not easy until I was checking on the internet when I saw a series of testimonies hearing people winning the Powerball lottery, I didn’t believed, but being poor no job you have no option. I gave it a try and I contacted Dr Kachi who told me what i have to do before I can become a big lottery winner and I accepted. He made special prayers for me in his temple and gave me the required numbers to play the lottery game and when I used the numbers to play it, I won a massive $344.6 million Powerball jackpot. I was so happy and I choose to review my winning in any platform, I would love other people to seek help from Dr Kachi through WhatsApp/number and Call: +1 (209) 893-8075 or email drkachispellcast@gmail.com by his website: https://drkachispellcast.wixsite.com/my-site

  • annadelaney41

    Nov 20, 2022

    I appreciate PINNACLE CREDIT SPECIALIST for their help with my credit score. We started late last month and in less than 18 days my negative items, credit card debt and evictions have been removed without any trace. They also increased my credit score from 582 to 811 excellent score. I can assure you PINNACLE CREDIT SPECIALIST is the best credit repair company who can fix your credit without asking for outrageous fees. Today I’m living a free life, with no worries about my credit report. I really appreciate PINNACLE for the job done on my credit report. They’re the best. You can contact: pinnaclecreditspecialist@gmail.com / +1 (480) 420 8331.

  • albertwalker922

    Nov 23, 2022

    Good day to all viewer online, my name is Albert Walker I am so overwhelmed sharing this great testimony on how i was checking for solution in the internet while miraculously i came across Dr Kachi who brought my ex Girlfriend back to me, This is the reason why i have taken it upon myself to thank this great spell caster called Dr Kachi, because through his help my life became more filled with love and i am happy to say that my ex Girlfriend who has been separated from me for the past 2years came back to me pleading for me to accept her back, This was a shocking to me my partner is very stable, faithful and closer to me than before, because before i contacted Dr Kachi i was the one begging my ex Girlfriend to come back to me but through the assistance of Dr Kachi, I now have my relationship restored. You can also have a better relationship only if you Contact Dr Kachi Website, https://drkachispellcast.wixsite.com/my-site OR Email: drkachispellcast@gmail.com You can reach him Call and WhatsApp Number:+1 (209) 893-8075

  • thomasgibson802

    Nov 24, 2022

    I want to use this opportunity to tell the whole world on how I become rich and famous. I’m 93 years old. I was passing through difficulty in business and there was no hope of me coming out of my debt. I borrow money in my bank to do my business and I run at lost on the business I got frustrated and decided to be playing lottery to see if I can win and make my business grow and I have played for years now nothing good is coming my way on till I meet someone online talking about Dr Ayoola on the internet. He was taking about how this Dr Ayoola help him to win mega million lottery game. I said to myself if this is true and decide to contact him and told him to help me as well I later read more about this man and see how he has been helping people all over the world. I have faith in him and choose to work with him. After working with him he told me what I need to do for the number to be given to me which I did after he finish working he said I will have a dream and the number will be review to me in the dream. That night has I was sleeping I dream a number immediately he call me and gave me the same number I dream of and ask me to go and play the number. Today I’m here testifying of the good work he did for me I played the number and I won the sum of 1, 000,000 million dollars in a lotto max. You can contact Dr Ayoola for help if you want to win big in lottery game he has the gift of giving right number contact him today and thank me email him today Via email: drayoolasolutionhome@gmail. com or https://www.facebook.com/Dr-Ayoola-105640401516053/ text or call +14809032128

  • waynadans

    Nov 25, 2022

    Hey everyone I bring to you good news.. Have been playing lottery for years now and unable to win I even came to conclusion that I won't play lottery again, last Monday I came online and I saw a post about Dr dominion spell lottery number I doubted but decided to give a last try and I reach out to him, we chatted to my greatest surprise on Thursday he cast a spell and gave me a winning number and i tried the numbers, guess what guys I won the lottery, my retired mom has be playing too and I have asked her to reach Dr dominion and I know soon she is going to win, if you want to win this lottery I will advice u reach on Dr dominion he has all it requires to make u win Email: dominionlottospelltemple@gmail.com website: https://dominionlottospell.wixsite.com/dr-dominion WhatsApp: +16574277820 Call: +12059642462