## Dijkstra’s algorithm

February 5, 2010 by Vignesh

Dijkstra’s algorithm used to solve shortest path problem.. Its used in routing…

For given source vertex(node) in the graph ,the alg will find the shortest path between the vertex and with every other vertex.

Ex: Finding shortest route between one city and all other cities..

Alg desc :

Entities :

Vertices- (nodes)

Edges -> links between vertices

Note : distance between 2 vertex is always positive..

All the vertices in the graph will be consider as unsettled vertices.. so we will maintain two sets (settled and unsettled)..Alg ends once all the vertices are in the settled set.Vertex will be moved to settled set,once its shortest distance has been found.

E -> Stores the shortest distance from the source to each vertex..

D -> store the predecessor of each vertex on the shortest path from the source..

X -> set of settled vertices, ie the vertices whose shortest distance from d source have been found

F- > unsettled Vertices..

E= $ -> represents infinity

D = () empty set

X = F = () empty set

add vertex to F

E(vertex) =0;

while F is not empty

{

vertex_A =find_minimum(F);

add vertex_A to X ;

find_neighbor(vertex_A);

}

find_minimum(F)

{

find the smallest (as defined by E) vertex in F

remove it from F and return it

}

find_neighbor(shortest_distance )

{

for each vertex_B adjacent to vertex_A, vertex_b not in X

{

if(d(vertex_B) > d(vertex_A) + [vertex_A,vertex_B] //shorter distance exists

{

d(vertex_B) = d(vertex_A) + [vertex_A,vertex_B]

D(vertex_B)=vertex_A

add vertex_B to F

}

}

}

More to add… soon i will update with an example and their run time as well as desc for complexity of this alg..

Source :

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

http://renaud.waldura.com/doc/java/dijkstra/

### Like this:

Like Loading...

*Related*

## Leave a Reply