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
has`A`

distance value with itself and infinite with every other node.`0`

- Add
to explored list which means`A,0`

is going to be explored. Since it is added to the explore list, it will not be further compared in the next steps.`A`

### Iteration#2

- Exploring the direct neighbors of
`A`

which are`B`

and`C`

, the rest of the nodes will remain the same. The value of`A (0)`

is added to the path cost of`B (10)`

giving the value of`B => 0+10=10`

. - Since the value
`10`

is less than the previous value of`B`

that was infinity in the above row, we will update its value which is 10. Similarly, the value of`C = (value of A + Pathcost (A → C))`

that is`0+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
`C`

has 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
`C`

has 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`

.

- Similarly, the value of
`D`

= Value of`C`

+ 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 of`E`

which was infinity and is updated by`5+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
`B`

is not the direct neighbor, its value will remain as it is. Nodes`A, C, and E`

are already in the explore list so these nodes will not be considered. - The remaining direct neighbor of
`E`

is`D`

. Value of`D`

= Value of`E`

+ Path Cost`(E → D)`

= 7 + 6 =**13.** - The value of
`D`

will be updated as it is less than its earlier value 14, in the above row. Here we have the minimum value 8 of node`B`

so it will be passed to the explore list.

### Iteration#5

- Now only
`D`

is 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.