Dijkstra’s algorithm is a minimization algorithm that is used to find the shortest paths in a graph. It is also known as the single source shortest path, which means it gives the least-cost path to each point from the source. It is mostly used in path searching and navigation applications such as Google Maps.
You may like: What is the Bellman-Ford Algorithm?
Implementation
Since it is implemented on the graphs, we will start from the source or starting node, and explore all its neighboring or directly connected nodes.
Consider the following directed graph:
| Steps | A | B | C | D | E | Explore |
| 1 | 0 | ∞ | ∞ | ∞ | ∞ | A,0 |
| 2 | – | 0+10= 10 | 0+5= 5 | ∞ | ∞ | C,5 |
| 3 | – | 5+3= 8 | – | 5+9= 14 | 5+2= 7 | E,7 |
| 4 | – | 8 | – | 7+6= 13 | – | B,8 |
| 5 | – | – | – | 8+1= 9 | – | D,9 |
Explanation
Now, let’s elaborate on each step in detail.
Iteration#1
- Initially, consider
Ahas0distance value with itself and infinite with every other node. - Add
A,0to explored list which meansAis going to be explored. Since it is added to the explore list, it will not be further compared in the next steps.
Iteration#2
- Exploring the direct neighbors of
Awhich areBandC, the rest of the nodes will remain the same. The value ofA (0)is added to the path cost ofB (10)giving the value ofB => 0+10=10. - Since the value
10is less than the previous value ofBthat was infinity in the above row, we will update its value which is 10. Similarly, the value ofC = (value of A + Pathcost (A → C))that is0+5 = 5, which is again less than the previous value that is infinity in the above row, so we will update it as well. - Now, since
Chas the minimum value(5)in the row, it will be added to the explore list, to be explored in the next step. As it has been added to the explore list, its value will not be considered in the next steps.
Iteration#3
- Now, since
Chas the minimum value(5)in the row, it will be added to the explore list, to be explored in the next step. As it has been added to the explore list, its value will not be considered in the next steps.- Value of B = Value of
C+ Path Cost(C → B) - Value of B = 5 + 3
- Value of B = 8 (less than the previous value of 10) so we will update the value of
B.
- Value of B = Value of
- Similarly, the value of
D= Value ofC+ Path Cost(C → D) = 5 + 9 = 14(less than the previous value, infinity), will also be updated. The same is the case with the value ofEwhich was infinity and is updated by5+2 = 7. - Here, the minimum value in the row is 7 of node
E, which will be added to the explore list, and will not be considered in the next comparisons.
Iteration#4
- Since
Bis not the direct neighbor, its value will remain as it is. NodesA, C, and Eare already in the explore list so these nodes will not be considered. - The remaining direct neighbor of
EisD. Value ofD= Value ofE+ Path Cost(E → D)= 7 + 6 = 13. - The value of
Dwill be updated as it is less than its earlier value 14, in the above row. Here we have the minimum value 8 of nodeBso it will be passed to the explore list.
Iteration#5
- Now only
Dis left as the directly connected node which has a value = 8 + 1 = 9, less than the previous value of 13 in the above row, so it will be updated. - Here we have only a single value that is 9 of node
D, so it will be shifted to the explore list. As a result, we have all the nodes in the explore list, which is the stopping condition.
Results
The minimum distance of each node from the source node is the calculated value of each node. That is;
- A → A: 0
- A → B: 5
- A → C: 7
- A → D: 8
- A → E: 9
Properties of Dijkstra’s Algorithm
- Dijkstra’s algorithm uses the greedy approach and provides optional solutions or paths.
- It works on both directed and undirected graphs.
Drawback of Dijkstra’s Algorithm
- It does not work for the graphs with negative edge weights.
