Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
1.1.
Different algorithms for shortest path 
2.
Djikstra’s Algorithm
3.
Applications of Dijkstra algorithm
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Dijkstra’s Algorithm

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction 

The shortest path issue in graph theory is the task of finding a path between two vertices (or nodes) in a graph that minimizes the sum of the weights of its constituent edges.

The challenge of determining the shortest way between two junctions on a road map may be described as a specific example of the shortest path problem in graphs, where the vertices correspond to intersections and the edges to road segments, each of which is weighted by the segment's length.

Different algorithms for shortest path 

The most important algorithms for solving this problem are

  1. With non-negative edge weight, Dijkstra's method solves the single-source shortest route issue.
  2. If edge weights are negative, the Bellman-Ford algorithm solves the single-source problem.
  3. The A* search algorithm uses heuristics to try to speed up the search for the single-pair shortest path.
  4. All-pairs shortest routes are solved using the Floyd–Warshall method.
  5. On sparse graphs, Johnson's technique solves all-pairs shortest routes quicker than Floyd–Warshall.
  6. With extra probabilistic weight on each node, the Viterbi algorithm solves the shortest randomized route issue

Djikstra’s Algorithm

We use the graph cost adjacency matrix, where cost is the edge's weight, represents the graph. The diagonal values in the graph's cost adjacency matrix are 0 because the source and destination vertex are the same. It is denoted by +∞ if there is no path from source vertex Vs. to any other vertex Vi. We assumed that all weights were positive in this algorithm. Dijkstra's algorithm never ends if the graph contains at least one negative cycle. By a negative cycle, we mean a cycle that has a negative total weight for its edges. Stepwise Implementation: 

  1. Create an empty set 'minCost' of size equal to the number of vertices to store the minimum cost to reach a particular vertex from the source vertex Vs. 
  2. Initially include the source vertex Vs. in set minCost and determine all the other direct paths from the source vertex Vs., without going through any other vertex. 
  3. Now include the nearest vertex in set minCost from the source vertex Vs. Again, find the shortest paths to all other vertex using this nearest vertex and update the values. 
  4. Keep repeating this step for n-1 times to include n-1 vertices, where n is the total number of vertices in the graph.  

 

After completing the above steps, we will get the shortest path to all other vertices from the source vertex. 

Example:

Find the Shortest path between P and Q in the given graph using Djikstra’s Algorithm.

Step 1: Make the empty set minCost, which will hold the shortest path from the source vertex P. 

Step 2:  Include the source vertex P in the set minCost, and find the direct shortest path to all other vertices without using any other vertex. 

minCost P A B C D Q
P 0 8(P) 4(K) 40(K)

Step 3:  Include the vertex nearest to P, which is C in this case, and again find the shortest path using vertex C, and update the values. 

minCost P A B C D Q
P 0 6(P,C) 14(P,C) 4(K) 16(P,C) 36(P,C)

Step 4:  Include the vertex 2nd nearest to P, which is A in this case, and again find the shortest path using vertex C and A, and update the values. 

minCost P A B C D Q
P 0 6(P,C) 14(P,C) 4(K) 14(P,C,A) 36(P,C)

Step 5:  Include the vertex 3rd nearest to P, which is B in this case, and again find the shortest path using vertex C, A, and B, and update the values.

minCost P A B C D Q
P 0 6(P,C) 14(P,C) 4(K) 14(P,C,A) 16(P,C,B)

Step 6: Again include the vertex next nearest to P, which is D in this case, and again find the shortest path using C, A, B, and D, and update the values. 

minCost P A B C D Q
P 0 6(P,C) 14(P,C) 4(K) 14(P,C,A) 16(P,C,B)

Since all the n-1 vertices are included, and hence we get the shortest distance between P and Q = 16, and the shortest path between P and Q is P->C->B->Q. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Applications of Dijkstra algorithm

  1. Google Maps Digital Mapping Services: We've all attempted to discover the distance between cities in G-Maps, or from your position to the next desired site. Because there are several routes/paths linking them, the Shortest Path Algorithm is used to discover the shortest distance between two points along the way. Dijkstra's Algorithm is used to determine the shortest distance between two points along the path. Consider India as a graph, with each city/place represented as a vertex and the route between two cities/places represented as an edge. Using this approach, the shortest paths between any two cities/places or from one city/place to another may be found.
     
  2. Social Networking Apps: You may have noticed that in many apps, the program proposes a list of friends that a certain user may know. What do you believe is the most efficient way for numerous social media businesses to integrate this functionality, especially when the system has over a billion users? The conventional Dijkstra method may be used to find the shortest path between users, which can be determined through handshakes or connections. When the social networking graph is tiny, it employs Dijkstra's algorithm and several other characteristics to identify the shortest pathways; however, as the graph grows larger, the normal technique takes several seconds to count, and other sophisticated algorithms are utilized.
     
  3. Designate a file server in a LAN: Dijkstra's algorithm may be used to designate a file server in a LAN. Consider the fact that sending files from one computer to another takes an endless amount of time. To reduce the number of "hops" between the file server and every other computer on the network, Dijkstra's method is used to find the shortest path between the networks with the fewest number of hops.
     

FAQs

  1. What is the time complexity of Dijkstra's Algorithm? 
    The time complexity of Djikstra's Algorithm is O(V^2), where V is the number of vertices, but we can reduce it to O(V + E(LogV)) using a min priority queue. 
     
  2. What is the space complexity of Dijkstra's Algorithm? 
    The space complexity of Dijkstra's Algorithm is O(V) because we are just using a single array or set for storing the minimum distance between the vertices, and its size will be equal to the number of vertices in the graph. 
     
  3. Which is the common data structure used to implement Dijkstra's Algorithm? 
    The most widely utilized data structure for implementing Dijkstra's Algorithm is a minimal priority queue because the required operations in Dijkstra's Algorithm match the specialization of a minimum priority queue

Key Takeaways

In this article, we have discussed the introduction to Dijkstra’s Algorithm and a detailed example. I hope you understand Dijkstra’s Algorithm properly. 

If you are a beginner, interested in computer fundamentals, and want to learn more about computer networks, you can look for our guided path, which is free! 

Thank you for reading. 

Until then, Keep Learning and Keep Coding.

Previous article
Regular and Bipartite graphs
Next article
Centrality Measure in Graph Theory
Live masterclass