Understanding Dijkstra’s Algorithm

Dijkstra’s algorithm or Dijkstra’s shortest path algorithm or single source shortest path algorithm is used in identifying the shortest path from starting node to a destination node in a weighted graph.

Dijkstra’s algorithm is quite similar to Prim’s algorithm for minimum spanning trees. Dijkstra’s shortest path algorithm works on a greedy approach, where the motive of the algorithm is to choose the solution with minimum cost.

The greedy approach-based algorithm always intends to select the solution which is optimized and efficient to cost, their main goal is to minimize the overall cost. Hence, Dijkstra’s algorithm does the same. A subgraph is a part or subset of a graph that is undirected and connected. The Dijkstra algorithm was published by a dutch scientist Edsger Dijkstra in 1959. 

In this article, we are going to discuss what is Dijkstra’s algorithm, the working of Dijkstra’s algorithm along with an example, then pseudo code for the algorithm, and will be concluding this article with the complexity and applications of the algorithm. 

Table of Contents

• What is Dijkstra’s algorithm?
• Working
• Example
• Pseudo Code
• Complexity
• Applications

What is Dijkstra’s Algorithm?

Dijkstra’s shortest path algorithm is similar to Prim’s algorithm for MST (Minimum Spanning Tree). In this algorithm, the shortest path is generated from the starting node to a target node. This algorithm also maintains two sets of vertices. One set comprises all the vertices included in the shortest-path graph and another set comprises all the vertices that are not included in the shortest-path graph yet. 

In every next step of Dijkstra’s algorithm, we will select a vertex (from the set of non-included vertices) which have the minimum distance from the source. This algorithm is different from the minimum spanning tree because this might not include all the vertices.

Explore free data structure and algorithms courses

Working of Dijkstra’s Algorithm

Dijkstra algorithm is applied on each step and follows the following steps:

1. Create a shortest path tree set; say U, this will keep a track of all the vertices included in the graph. The vertex included in this set will have the minimum distance from the destination. So, the minimum distance for each vertex is calculated and finalized accordingly. The set is empty at the start. 
2. First, assign a distance value to all the nodes/vertices of the input graph. 
3. Initialize all vertices with an INFINITE distance value.
4. Set the source vertex’s distance value to zero.
5. While U (shortest path tree set) doesn’t include all the vertices.
   1. Choose a vertex u that is not present in U and has a minimum distance value. 
   2. Include u in U. 
   3. Now, update the distance value of u in all the adjacent vertices. 
      1. For updating the distance value, iterate this in all adjacent vertices. 
      2. For each adjacent vertex v, if the weight of edge u-v and the sum of the distance value of a is less than the distance value v, then update the distance value a.

This algorithm can be derived to the main formula, which is 

if d(u) + c(u, v) < d(v)

   d(v) = d(u) + c(u,v)

This means if the sum of distance of u (source vertex) and the cost of going from u to v(adjacent/ destination vertex(initialized as infinite)) is less than the distance value of v. Then, the distance of v becomes the sum of the distance of u (source vertex) and the cost of going from u to v.

Example

Consider the following graph, and calculate the shortest path between A and all other vertices. 

Solution: Initially, the cost of every vertex from A will be infinite or unknown, and the distance value from A to A will be 0.

Source	Destination
A	B	C	D	E	F
	∞	∞	∞	∞	∞

Now, let’s find the distance between A and B. Putting these into the above relaxation formula, Check, d(u) + c(u, v) < d(v)

i.e.  d(A) + cost (A, B)< d(B)

    = 0 + 7 < ∞       //True

So, d(B) = d(A) + cost (A, B)

              = 7

Now, updating the table

Source	Destination
A	B	C	D	E	F
	∞	∞	∞	∞	∞
	7	∞	∞	∞	∞

Now, let’s find the distance between A and C. Putting these into the above relaxation formula, Check, d(u) + c(u, v) < d(v)

i.e.  d(A) + cost (A, C)< d(C)

    = 0 + 9 < ∞       //True

So, d(C) = d(A) + cost (A, C)

              = 9

Now, updating the table

Source	Destination
A	B	C	D	E	F
	∞	∞	∞	∞	∞
	7	9	∞	∞	∞

Now, let’s find the distance between A and F. Putting these into the above relaxation formula, Check, d(u) + c(u, v) < d(v)

i.e.  d(A) + cost (A, F)< d(F)

    = 0 + 14 < ∞       //True

So, d(F) = d(A) + cost (A, F)

              = 14

Now, updating the table

Source	Destination
A	B	C	D	E	F
	∞	∞	∞	∞	∞
	7	9	∞	∞	14

Now, the minimum cost between A and B is 7, which is minum an dno need to update that. Now, let’s check cost of other adjacent node with respect to A via B. 

Cost of reaching C from A via B is 17, which is more than previous cost. So we will not update then. 

Cost of reaching F via B, as there is no direct link so no changes will be done

Source	Destination
A	B	C	D	E	F
	∞	∞	∞	∞	∞
	7	9	∞	∞	14
(A,B)	7	9	∞	∞	14

Now, let’s check the cost of reaching vertex D from A via B. The path will be A-B-D, and the cost is 22. Updating this on table, we will get

Source	Destination
A	B	C	D	E	F
	∞	∞	∞	∞	∞
	7	9	∞	∞	14
(A,B)	7	9	∞	∞	14
	7	9	22	∞	14

The minimum cost between A and B is fixed now which is 7, so now we will choose next minimum cost which is 9. So now we will check the cost of adjacent node via B and C. 

So, the cost of reaching D via C is 20 which is minimum then previous..

Also, the cost of reaching F via C is 11, which is also small then previous.

 So, the updated table will be

Source	Destination
A	B	C	D	E	F
	∞	∞	∞	∞	∞
	7	9	∞	∞	14
(A, B)	7	9	∞	∞	14
(A, B, C)	7	9	20	∞	11

Now, the minimum cost between A and C is fixed which is 9, hence will be choosing next minimum which is 11 among 20, infinity and 11. 

Now, we will check all the adjacent node with respect to A, B, C, F

There is a path A-C-F- E, whose cost is 20. 

Checking all other nodes, to reach. No minimum cost found. 

Source	Destination
A	B	C	D	E	F
	∞	∞	∞	∞	∞
	7	9	∞	∞	14
(A, B)	7	9	∞	∞	14
(A, B, C)	7	9	20	∞	11
(A, B, C, F)	7	9	20	20	11

Now, 11 is also fixed, selecting any one of D and E because both are 20. 

Let’s say selecting D and checking all the nodes with respect to (A, B, C, D, F), but we will get the same values as the minimum one. 

Hence the cost between source to destination can be represented as 

Source	Destination
A	B	C	D	E	F
	∞	∞	∞	∞	∞
	7	9	∞	∞	14
(A, B)	7	9	∞	∞	14
(A, B, C)	7	9	20	∞	11
(A, B, C, F)	7	9	20	20	11
(A, B, C, F, D)	7	9	20	20	11

Explore Free Online Courses with Certificates

Pseudo Code

DIJKSTRA (G, w, s)

A(G, s)                //Initialize-single source

S ← Ø

Q ← V[G]

while Q ≠ Ø

do u ← EX-MIN (Q)   // Find minimum distance value

S ← S ∪ (u)

for each vertex v є Adj[u]

do RELAX (u, v, w)

Complexity of Algorithm

Dijkstra’s algorithm takes O (A log B) time to find the shortest path for any graph.

Where A is the number of edges and B is the number of vertices. 

It requires O(B) space complexity. 

Applications of Dijkstra’s Algorithm

1. It is used in finding the shortest path. 
2. It is used in social networking applications
3. Find air-route.
4. Identifying locations on the map.
5. In telephone network. 

Contributed by: Kanika Joshi