Facebook

Dijkstra’s algorithm

Dijkstra's algorithm is way of finding shortest path from a source vertex to sink in a given connected and weighted graph. It is somewhat similar to Prim's algorithm and it works for directed as well as undirected graphs. The step by step process is specified below :

  1. Source vertex is chosen and marked.
  2. Mark distances at all vertices as infinity and at source vertex as 0.
  3. Update the distances of adjacent vertices from infinity by given distances on the graph .
  4. We look for minimum distance value from source vertex to adjacent vertices.
  5. The minimum distance is chosen and next vertex is marked.
  6. Look for the adjacent vertices of marked vertex.
  7. Replace the distance if it is less than the mentioned value at the vertices.
  8. Keep on following the same procedure until shortest path to sink is obtained.

 

Example:

Consider a weighted and undirected graph as shown in Fig 1

 

Screen Shot 2014-08-11 at 1.37.58 PM
Fig 1 : A Graph

 

  • Choose a source vertex.In Fig 2 ,a is chosen as the source vertex.
  • Mark all the distances at vertices as infinity initially and distance of source vertex as 0
Screen Shot 2014-08-11 at 1.42.33 PM
Fig 2: Mark infinity at all vertices and 0 at the source.

 

  • Look for neighbors of source vertex a.(Fig 3).
  • b and i are the adjacent vertices.
  • Update the distance at b from infinity to 4 and at i to 8.
  • Find the minimum distance from a.
  • 4 is smaller than 8 so b is the next marked vertex.
Screen Shot 2014-08-11 at 1.44.47 PM
Fig 3:Update b ,i ,mark vertex b and Edge(a,b)

 

  • Look for the neighbors of b.
  • c and i are the adjacent vertices.
  • Update value at c from infinity to 12(4+8) as distance from source to c is 12.(Fig 4)
  • Distance from a to i through b is 15(11+4)  and a to i directly is 8.So 8 is not updated.
  • Look for next min distance  to a vertex and do not count already marked vertices and edges.
  • The distance at c is 12 and at i is 8,so i  is marked.
Screen Shot 2014-08-11 at 1.48.52 PM
Fig 4 : Update c to 12 and mark vertex i

 

  • Look for neighbors of i .
  • Update distance at h to 15(8+7) and at g to 9.
  • Distance from source a to b is 4 and a to b through i is 19 so it is not updated.
  • Look for next minimum distance from marked vertices.
  • 12,15,9 are the respective distances from marked vertices.
  • Mark vertex g and Edge(i,g) as 9 is the minimum distance from source a to g through i.
Screen Shot 2014-08-11 at 1.52.02 PM
Fig 5 : Mark g

 

  • Look for neighbors of g.
  • The distance at h from a through i  is 15 and from a through  i and g is again 15 so it is not updated(Fig 6).
  • The distance from a to f through i and g is 11.So update it by 11.
Screen Shot 2014-08-11 at 1.59.22 PM
Fig 6 : Update distance at f to 11
  • Look for the next minimum distance(Fig 7).
  • 12,15,11 are the distances from marked vertices.
  • Mark f and Edge(g,f) as distance is minimum.
Screen Shot 2014-08-11 at 2.01.26 PM
Fig 7 : Mark f
  • Neighbors of f are c,d,e.
  • Distance at c is not required to be updated.
  • Update distance at d to 25(11+14) and at e to 21(11+10)(Fig 8).
  • Look for minimum distance.
  • 12,15,19,21 are the distances available for consideration.
  • Mark vertex c as 12 is minimum.
Screen Shot 2014-08-11 at 2.02.43 PM
Fig 8 : Mark c

 

  • Distance of neighbors of c is not required to be updated.
  • Mark d and then e.(Fig 9)
Screen Shot 2014-08-11 at 2.06.17 PM
Fig 9 : Mark d and e.

 

The following table gives the details of dijkstra's algorithm applied on Fig 1.The shortest path from a to e is {a,b,i,g,f,c,d,e} with minimum cost of 21.

Screen Shot 2014-08-11 at 4.35.16 PM
Fig 10
Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar