Table of Contents
Introduction to Dijkstra Algorithm
The Dutch Computer scientist Edsger William created the algorithm in 1956. It’s used to determine the most efficient route from the vertex (source node) to any (or any) other vertex of the graph. A graph is simply the connection of vertices to the edges. The algorithm is sometimes known as Single Source Shortest Path Algorithm because of its implementation.
Application – Usage of Dijkstra Algorithm
Before we dive into any algorithm, it is vital to comprehend the actual uses of the algorithm. Most of the problems we face in everyday situations involve solving the shortest route problems based on the shortest path. To put it in terms that are easy to understand, you need to go from city X to Y. Each town is connected via numerous routes. What is the path we usually prefer? No question, we’d choose the one that will help us get there at the most nominal costs and time!
What are the principal uses of Dijkstra’s Algorithm:
- The Dijkstra algorithm is mostly used to find the shortest route between two destinations, A to B. It is widely used in real-life applications like Google Maps.
- This algorithm is also widely used in searching for the shortest route in networking and telecommunication domains to minimize transmission delay.
- The algorithm is utilized wherever you come across the requirement for shortest path solutions, whether in transportation, robotics embedded systems, factories, or production facilities, to identify flaws, etc.
Explanation – Working on Dijkstra Algorithm
The Dijkstra Algorithm allocates the cost value from the source (starting vertex) to the destination vertex to find the shortest path between two destinations. The cost value can be considered as distance, money, and time is taken to reach the source to the destination vertex.
Steps to be followed for solving using Dijkstra’s algorithm:
- Convert a problem to a graph representation.
- Create a list of unvisited vertices and assign a vertex as ‘source’ and after that allocate a maximum possible cost (infinity) to all other vertices. The cost of the source to itself will be zero as it actually takes nothing to go to itself.
- Every step of the algorithm tries to minimize the cost for each vertex from the source vertex to the destination vertex.
- For every unvisited neighbor (V2, V3) of the current vertex (V1) calculate the new cost from V1.
- The new cost of V2 is calculated as follows:
Minimum(existing cost of V2 , (sum of cost of V1 + the cost of edge from V1 to V2)) - When all the neighbors of the current vertices are visited and the cost has been calculated, mark the current node V1 as visited and remove it from the unvisited list.
- Select the next vertex with the smallest cost from the unvisited list and repeat from step 4.
- The algorithm finally ends when there are no unvisited nodes left.
Problem – Dijkstra Algorithm Example
Check out what the below map shows. The houses have been chosen and are arranged from alphabets A through F. Each edge comes with a distance.
We must travel between house ‘A’ to all destinations and determine the most efficient routes with the least distance from house ‘A’ to other places.
Solution – Dijkstra Algorithm shortest path problem
Convert the problem to its graph equivalent.
Now, we will get the following representation. The graph is weighted and undirected, and each city has been replaced with the alphabet associated with it, and the edges also have the cost (to transfer from one point to the next) shown on the graph.
Assign a cost to vertices
Assign a cost of 0 to the source vertex and ∞ (Infinity) to all other vertices, as shown in the image below.
Maintain a list of unvisited vertices. Add all the vertices to the unvisited list.
Calculate the minimum cost for neighbors of the selected source
For each neighbor A, C, and D of the source vertex selected (B), calculate the cost associated with reaching them from B using the formula. Once this is done, mark the source vertex as visited (The vertex is now blue to indicate that it was visited).
Minimum(current cost of neighbor vertex, cost(B)+edge_value(neighbor,B))
For neighbor A: cost = Minimum(∞ , 0+3) = 3
For neighbor C: cost = Minimum(∞ , 0+1) = 1
For neighbor D: cost = Minimum(∞ , 0+6) = 6
Select the next vertex with the smallest cost from the unvisited list
Choose the unvisited vertex with minimum cost (here, it would be C), consider all its unvisited neighbors (A, E, and D), and calculate the minimum cost for them.
Once this is done, mark C as visited.
Minimum(current cost of neighbor vertex, cost(C)+edge_value(neighbor,C))
For neighbor A: cost = Minimum(3 , 1+2) = 3
For neighbor E: cost = Minimum(∞, 1+4) = 5
For neighbor D: cost = Minimum(6 , 1+4) = 5
Observe that the cost value of node D is updated by the new minimum cost calculated.
Repeat step 4 for all the remaining unvisited nodes
Continue step 4 until there are all unvisited nodes left. After the procedure, we’ll be able to determine the shortest path from vertex B that originates to all other vertices. The final version of the graph could look like the one shown below.
Evidence of the Correctness
What can we do to ensure that the algorithm used by Dijkstra gives us the most efficient possible path between nodes? Let’s look at the following explanation to find out if Dijkstra always offers us the most efficient route. Take a look at the following terms:
D(s,u) = the minimum distance as calculated by Dijkstra’s algorithm between nodes s and u
d(s,u) = the actual minimum distance between nodes s and u
According to Dijkstra’s Algorithm, D(s,u) = d(s,u)
Proof:
- Let us start by assuming that Dijkstra’s Algorithm is incorrect.
- This means there would be some vertices left when a vertex u is included into the Visited List which indicates => D(s,u) > d(s,u)
- Let x be the first of these vertices that was pushed into the Visited List. Then,
- When node x is included into the Visited List: D(s,x) > d(s,x)
- This implies that all previous vertices, say z that were included into the Visited List signifies D(s,z) = d(s,z)
- Let’s look at the moment when this node x is included into the Visited List.
- Let P be the (real) shortest path from s to x
- Let z be the first node that is not in the “Visited List” and is along the shortest path.
- Let y be the predecessor node of z on the shortest path P
- Have a look at the diagram below for better understanding:
- We can conclude the following:
- D(s,y) = d(s,y) … (1) (This means the minimum distance s to y computed by the algorithm = actual min. distance s to y as y is included before x)
- D(s,z) = D(s,y) + edge_cost(y,z) = d(s,y) + edge_cost(y,z) … (2)
- D(s,x) ≤ D(s,z) …(3) (Because the next vertex included by the algorithm is x)
- We can now finally deduce that:
D(s,x) ≤ D(s,z) … From (3)
= d(s,y) + edge_cost(y,z) … From (2)
≤ d(s,y) + edge_cost(y,z) + d(z,x)
= d(s,x)
- The above result contradicts the assumed fact of Dijkstra’s algorithm being incorrect earlier.
- Hence, by proof of contradiction, we can say that Dijkstra’s algorithm always gives us the shortest possible path between 2 nodes which is: D(s,x) should be equal to d(s,x)
Additional Information
- The demo in the example was designed using undirected graphs. However, Dijkstra’s Algorithm is also a good choice for directed graphs.
- The shortest path doesn’t traverse all vertices. In addition, there may be more than one shortest path between two nodes.
- Dijkstra’s Algorithm isn’t a suitable solution for graphs with opposite (negative) edges. Algorithms such as the Bellman-Ford Algorithm can be applied in the cases in question.
If you find anything incorrect in the above-discussed topic and have further questions, please comment below.
Connect on:
