Dijkstra’s algorithm

http://install4install.com

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.It works for directed as well as undirected graphs.

 

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

 

Screen Shot 2014-08-11 at 1.42.33 PM

Fig 2: Mark infinity at all vertices and 0 at the source.

 

Screen Shot 2014-08-11 at 1.44.47 PM

Fig 3:Update b ,i ,mark vertex b and Edge(a,b)

 

Screen Shot 2014-08-11 at 1.48.52 PM

Fig 4 : Update c to 12 and mark vertex i

 

Screen Shot 2014-08-11 at 1.52.02 PM

Fig 5 : Mark g

 

Screen Shot 2014-08-11 at 1.59.22 PM

Fig 6 : Update distance at f to 11

Screen Shot 2014-08-11 at 2.01.26 PM

Fig 7 : Mark f

Screen Shot 2014-08-11 at 2.02.43 PM

Fig 8 : Mark c

 

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



Short URL: http://tinyit.cc/eff02d
Author: Cusp2207 on August 12, 2014
Category: Algorithms, Computer Science
Tags:

Leave a Reply

Last articles