DIJKSTRA ALGORITHM USING GREEDY APPROACH | ANALYSIS DESIGN OF ALGORITHM (ADA)

📌Highlights: Hi Friends ! In this post , I discuss about Dijkstra Algorithm which is also known as Single Source Shortest path Algorithm using greedy approach.I will explain all the working procedure of algorithm by taking an example.

Let we understand what is it,

Dijkstra algorithm is also known as single source shortest path  algorithm. The main purpose of this algorithm is to find shortest path form a given graph.

If a waited graph is given than we have to find shortest path from some starting vertex.

Point to be noted 

1. Dijkstra algorithm works only for connected graphs.

2. Dijkstra algorithm works only for those graphs that do not contain any negative weight edge.

3. The actual Dijkstra algorithm does not output the shortest paths.

4. It only provides the value or cost of the shortest paths.

5. Dijkstra algorithm works for directed as well as un-directed graphs.

Let us say I am selecting vertex 1 to find shortest path to all vertices may be a direct path from other vertices and  I can select any of the vertex as a source vertex as we have to find out the shortest path.

It is a minimization problem and a minimization problem is an optimization problem. So optimization problem can be solved using greedy method.

Greedy method say that if the problem is solve through stage one step at a time or considering one input at a time to get a optimal solution. In greedy method there are pre define procedure and follow those procedure to get optimal solution. So Dijkstra algorithm is a procedure to give the optimal solution that is minimum result which is shortest path.

let we understand the working of Dijkstra algorithm by the help of an example.

Now here the initial or starting node is A.

Put cost of each vertex such as [ A, B, C, D, E ]

Cost of vertex are [ 0, ∞, ∞, ∞, ∞ ]

Cost of A vertex is 0 because it starting vertex just like we are not spending any cost ∞.

Now find all adjacent / Neighbour vertex of A are [A to B] & [A to C].

We assume the cost of B = infinity and cost of C = infinity.

Now the new cost of B= (4+0)=4 and C=(1+0)=1.

Compare the new cost to old cost such as:

Vertex      [B , C]

old cost    [∞, ∞]

New cost  [4 , 1]

So here the new cost is smaller than old cost so we update the cost of B & C to [4 , 1]. respectively.

Now we compare cost of all vertices except A for finding the next smallest cost such as:

 Vertices :  [ B , C , D , E ]

 Cost      :  [ 4 , 1 , ∞, ∞ ]

Here minimum cost is 1.So we select C for next move.

Now we find all neighbour vertices from C vertex except A.

here neighbour vertices are [ B , D ]

Now find new cost for [ B , D ]

For C to B : 7 + 1 = 8 

For C to D : 2 + 1 = 3

Now compare this new cost to old cost and update to new cost if new cost is minimum otherwise leave as it is.

Vertices   : [B , D]

Old Cost  : [4 , ∞] 

New Cost : [8 , 3]

So here old cost from C to B is 4 which is less than new cost i.e 8 so no need to update old cost leave it as it is.

and old cost of C to D is maximum i.e ∞ , so update with new cost i.e 3.

we get:

Now we compare cost of all vertices except A for finding the next smallest cost such as:

 Vertices :  [ B  , D , E ] 

 Cost      :  [ 4  , 3 ,∞ ]

Here minimum cost is 3.So we select D for next move.

Now we find all neighbour vertices from D vertex except A & C.

here neighbour vertices are [ B , E ]

Now find new cost for [ B , E ]

For D to B : 5 + 3 = 8 

For D to E : 7 + 3 = 10

Now compare this new cost to old cost and update to new cost if new cost is minimum otherwise leave as it is.

Vertices   : [B , E]

Old Cost  : [4 , ∞] 

New Cost : [8 ,10]

So here old cost from D to B is 4 which is less than new cost i.e 8 so no need to update old cost leave it as it is.

and old cost of D to E is maximum i.e ∞ , so update with new cost i.e 10.

we get:

Now we compare cost of all vertices except A,C & D for finding the next smallest cost such as:

 Vertices :  [ B  , E ] 

 Cost      :  [ 4  ,10 ]

Here minimum cost is 4.So we select B for next move.

We get,

Now we find all neighbour vertices from D vertex except A , C & D.

here neighbour vertices are [ E ]

Now find new cost for [ E ]

For B to E : 4 + 1 =5 

Now compare this new cost to old cost and update to new cost if new cost is minimum otherwise leave as it is.

Vertices   : [ E ]

Old Cost  : [10 ] 

New Cost : [ 5 ]

So here old cost of E is 10 which is more than new cost i.e 5 so we need to update old cost to new cost i.e 5.

we get:

Finally we get:

Now we get the minimum cost for all vertex from A.

Now we find what is the shortest path from A to E.

Follow the following diagram:

Make a matrix for cost from vertex A.

STEP 1

Now start from A and write cost of [B,C,D,E] from A in matrix.

Note write ∞ if there is no direct edge available. 

Form above find the minimum cost i.e C=1 so select vertex C and write C in left side of matrix.we get

STEP 2

Now we will find all cost of edge from vertex C.

Direct edges from C is C to B and C to D and C to A but we will not consider C to A it done. 

Now find the cost of direct edge:

C to B =7 + old cost of C (cost of selected vertex)

         =7 + 1= 8

C to D =2 + old cost of C (cost of selected vertex)

         = 2 + 1 =3

C to E is indirect edge so write as ∞ 

so matrix will we

Now in above matrix we 4 from C to B but the calculated cost is 8 which is greater than 4 so we write as it is as above.

already selected will be -- such as C.

Now here 3 is minimum value among all so select it i.e vertex D and write it to the left side of matrix.

STEP 3

Now find direct edge from D which is D to B and D to E.

Now calculate the cost

D to B = 5 + old cost of D (cost of selected vertex)

          = 5 + 3

          = 8  

D to E = 7 + old cost of D (cost of selected vertex)

          = 7 + 3

          = 10

So here in matrix old cost of B is 4 and new cost is 8 which is greater than 4 so we take 4 that means consider old value.

old cost of E is ∞ and new value is 10 which is smaller than ∞  so we take 10.

Now the matrix will be:

STEP 4

Now find direct edge from B which is B to E.

Now calculate the cost

B to E = 1 + old cost of B (cost of selected vertex)

         = 1 + 4

         = 5

Now we get new cost E is 5 compare it to the old cost of E i.e 10 which is greater than 5 so we take 5

so the matrix will be

So the shortest path from A to E will be A→C→D→B→E. 

So Friends ! Now this is all about the working of Dijkstra's algorithm. I hope this example is helpful for understanding the working of Dijkstra's algorithm.We will meet in new post till continue reading...