Feeds:
Posts

## Dijkstra’s algorithm

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)

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

E(vertex) =0;
while F is not empty
{
vertex_A =find_minimum(F);
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