• 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

  • stephaniewilson1906654f43d6b8864b31

    Feb 23, 2024

    Hello everyone, I’m Stephanie Wilson from Florida. My score was 598. After quick research of a hacker called PINNACLE CREDIT SPECIALIST with numerous recommendations and that which my girlfriend Tabitha explained about with positive reviews. I contacted him explaining my problem. Duly he came up with a resounding proposal and guaranteed to fix my credit. Today I got a score alert of 803!!! The last baddie was finally removed!!! A collection that I never owed to begin with. It's amazing now all thanks to PINNACLE CREDIT SPECIALIST. I strongly recommend him for your credit fix. PINNACLECREDITSPECIALIST@GMAIL.COM / +1 (409) 231-0041.

  • davidstarks809a80a6eefce0247db

    Feb 24, 2024

    Hello everyone, all thanks to PINNACLE CREDIT SPECIALIST long story short, a divorce during covid really hampered my credit. I went from the mid-700s to the 500s. I’ve been trying to work hard to get it built back up and have recently got as high as 660 on some bureaus. I recently sent dispute letters for a few items and two of them caused my score for Equifax to drop significantly. It was so disheartening. My first dispute was with Ally Financial. Last year, I had a lot of building up in one month, so I requested a payment extension for them for that month. They agreed to give me one so long as I would pay an extension fee by a due date that they’ve given. I absolutely did that right away and paid what they asked of me. However, by the time everything got processed, it was considered a late payment for that month, which is what I was trying NOT to do. I’ve called their customer service, and they said there’s nothing they could do to remove it because that would be reporting an inaccurate credit report. I tried to dispute it with a letter and once they received it and investigated it, my score dropped 19 points from them. I also had issues with Discover bank. I had a charge off that occurred in 2021. My credit reports have always shown a past due balance, even though it’s charge off, and stupidly I listen to a lot of internet videos, saying that you could dispute past due balance on charge offs because they are not accurate. When I did that, I got an update on my Equifax saying that the scriptures were added to my Discover account and it showed my score dropping 39 points. I didn’t understand or know how I could go about fixing my credit. I read about PINNACLE CREDIT SPECIALIST on QUORA and CK and informed me, I contacted them after reading some testimonies about them, they raised my credit score to 802 and deleted all negative items on my credit report within 6 days. They made it work and I have a clean credit profile now. My heart is full of gratitude. You can reach them by email: PINNACLECREDITSPECIALIST@GMAIL.COM OR Call +1 (409) 231-0041.

  • carolgreene50269733fb461a14461

    Feb 26, 2024

    I had to contact PINNACLE CREDIT SPECIALIST by their email: PINNACLECREDITSPECIALIST@GMAIL.COM and +1 (409) 231-0041. I have been working on rebuilding my credit after my divorce. I had 5 charge offs, I have four opened cards, only one if they have a balance but it's nearly maxed out. I had a CO with Amex from several years ago that is due to fall off in June with TU. I had other CO’s and collections from my divorce that took me from high 700s Fico to low 500’s. I was really in an embarrassing financial situation due to my poor Fico score which led me to meeting some imposters online who claimed to help but worsened my problems. I needed to raise my score a bit higher. It eventually paid off when I met PINNACLE CREDIT SPECIALIST through a reference online (may God bless him). His work rate, professionalism and discretion are top-notch. He increased my scores and the negative items on my report in a relatively short time (6 business days) which finally got me the mortgage for my new house. Tell him I referred you to him…. All the Best!

  • erikcooper28263eaf2a32fbc4823

    Feb 29, 2024

    I was in the process of purchasing a house and they were something that was hurting my credit. Some of these items that were hurting my credit are: Affirm (30 days late 3/2023), Affirm (30 days late 4/2023), First Premier (scheduled to be removed 3/2024), Rent Recovery (Paid Collection) Never received prior notification of a debt. I asked this community because you guys are awesome with your advice, and I have been successful. A guy named David from this community spoke well about a credit expert called PINNACLE CREDIT SPECIALIST who helped him remove medical bills and raised his score to 780 in a few days. I emailed him on: PINNACLECREDITSPECIALIST@GMAIL.COM and he responded ASAP asking me to text him on his personal number +1 (409) 231-0041 for further discussion. Well, I did and eventually got started with the project with him. I was amazed after a few days he pulled through for me and removed all my late payments and raised my score to 811. I just purchased the home of my dream, all thanks to him and his team for helping me. Contact him with the above email and number for your credit repair.

  • lilabradley4890c6324981eb64361

    Mar 01, 2024

    Hey all!! You don’t know how relieved I am right now. I’ve been literally living on this forum for about 2 years learning everything I can to rebuild my credit. I was really in an embarrassing financial situation due to my poor credit score. When I started my scores were in the 560 range, everything was wrecked. Few days after I came across PINNACLE CREDIT SPECIALIST on this forum and contacted them, they increased my score and improved my credit profile by removing the evictions, charge off, late payment and DMV, today my Fico 8 are TU: 831, EX: 827, EQ: 769. Honestly, I don’t enjoy writing much, but I must let the world know about this genius that helped me. I sincerely acknowledge their relentless efforts and urge you to contact PINNACLE CREDIT SPECIALIST for any credit related issue. Contact info: PINNACLECREDITSPECIALIST@GMAIL.COM Or call +1 (409) 231-0041. Thanks.

  • Cindy Jason

    Mar 03, 2024

    HOW TO GET YOUR EX HUSBAND BACK HELP OF DR KACHI CALL NUMBER +1 (209) 893-8075 God did it for me again with the help of Dr Kachi with his love spell to get my husband back. we divorce 3months ago and since things become so hard for me because I love my husband so much, But he was chatting on me with another woman and he always goes to party every night my husband doesn't care about me whenever he get back at night he will be beating me up with no reason, I cry every night and day to get my husband back to his normal love and affection that he give to me before. but nothing was working out for me I try my best I left him with my kids but I couldn't sleep at night without thinking about my husband, then one day I was reading a new online about our politics and I see a comment about Dr Kachi how he restored broken relationship back and marriage, i didn't believe in love spell at the first place, then i have to make further research about Dr Kachi I opened his website I can't believe what I saw a great man helping people return their lover back and being happy in relationship again. I went fast and contacted Dr Kachi to help me restore my marriage back, after I provided the required needed to cast the love spell, the next day my husband come back to me and apologies for him leaving me and the kids Dr Kachi made me the happiest woman on earth I am so happy, I do appreciate your kind help bring my husband home, you can also contact him and seek for help in break up in married Via Text Number WhatsApp: +1 (209) 893-8075 Website: https://drkachispellcaster.wixsite.com/my-site Email drkachispellcast@gmail.com

  • Cindy Jason

    Mar 03, 2024

    HOW TO GET YOUR EX HUSBAND BACK HELP OF DR KACHI CALL NUMBER +1 (209) 893-8075 God did it for me again with the help of Dr Kachi with his love spell to get my husband back. we divorce 3months ago and since things become so hard for me because I love my husband so much, But he was chatting on me with another woman and he always goes to party every night my husband doesn't care about me whenever he get back at night he will be beating me up with no reason, I cry every night and day to get my husband back to his normal love and affection that he give to me before. but nothing was working out for me I try my best I left him with my kids but I couldn't sleep at night without thinking about my husband, then one day I was reading a new online about our politics and I see a comment about Dr Kachi how he restored broken relationship back and marriage, i didn't believe in love spell at the first place, then i have to make further research about Dr Kachi I opened his website I can't believe what I saw a great man helping people return their lover back and being happy in relationship again. I went fast and contacted Dr Kachi to help me restore my marriage back, after I provided the required needed to cast the love spell, the next day my husband come back to me and apologies for him leaving me and the kids Dr Kachi made me the happiest woman on earth I am so happy, I do appreciate your kind help bring my husband home, you can also contact him and seek for help in break up in married Via Text Number WhatsApp: +1 (209) 893-8075 Website: https://drkachispellcaster.wixsite.com/my-site Email drkachispellcast@gmail.com

  • patricianelson0529f9ed2c49f224ae8

    Mar 05, 2024

    My name is Patricia Nelson. I was in the process of rebuilding credit from divorce and unfortunately had my car totaled otherwise I would’ve kept my current auto loan and car. Previously I had Experian FICO around 674, with a similar auto score. My TransUnion was absolutely trashed, and barely 600 and my Equifax was in the 640s. I had no collection accounts, no charge offs, and two accounts paid less than agreed. I tried getting a loan on PNC but got denied. I needed help and found PINNACLE CREDIT SPECIALIST here, they're a good and kind credit repair team. They pulled my score to 801 Experian, 805 TransUnion, 809 Equifax and they added good trade lines to my credit report. I got everything I wanted and even more. Thanks to the entire team. Contacts: PINNACLECREDITSPECIALIST@GMAIL.COM / +1 (409) 231-0041.

  • richardmorin461babb0c03826f498d

    Mar 12, 2024

    Today I called PINNACLE CREDIT SPECIALIST and asked to have my BK7 removed from my CR, and they did. It was scheduled to fall off next year. So that’s that. A horrible chapter in my life but I’ve come out on top. So much wiser, better prepared for the future, and peace of mind where finances are concerned. Thanks to this forum and the good folks that spend their time here to share their experience and share the knowledge they got from PINNACLE CREDIT SPECIALIST. Thank you PINNACLE CREDIT SPECIALIST for all your assistance, guidance and cheerleading. Especially in the early days of my rebuild. With my scores now in the 800’s I’m tempted to app just to know I’d likely be approved, but there’s nothing I need right now. A sincere thanks to all of you! Contact them by email: PINNACLECREDITSPECIALIST@GMAIL.COM / Or call +1 (409) 231-0041.

  • jasonherman4787bb771ddefc64bc2

    Mar 13, 2024

    Hi everyone, I want to sincerely appreciate PINNACLE CREDIT SPECIALIST for the dedication and time they put in working my credit. I had 4 charges off accounts (3 cc and 1 installment loan). I do have 2 cards with longevity and bad payment history though lower limits ($1200 and $850) and a car loan with 7 late time payments reflecting. During my financial struggles NFC closed the 2-credit card accounts I had with them. I also had a chapter 7 BK in 2020. I did have high utilization and few late payments (over more than 10 days late). The account closure dropped my scores because the balances took my utilization to 990%. I continued making payments on time until a friend read about PINNACLE CREDIT SPECIALIST on Quora and informed me, I contacted them after reading some testimonies about them, they ran my credit report, analyzed my credit score and determined which action will have the greatest impact. They raised my credit score to 803 and deleted all negative items on my credit report including the chapter 7 BK, within 6 days. They made it work and I have a clean profile now. My heart is full of gratitude. You can reach them via: PINNACLECREDITSPECIALIST@GMAIL.COM Or call +1 (409) 231-0041.