Dijkstra's algorithm, Data Structure & Algorithms

Q. Explain Dijkstra's algorithm for finding the shortest path in the graph given to us.

 Ans:

The Dijkstra's algorithm: This is a problem which is concerned with finding the least cost path from an originating node in a weighted graph to a destination node in that particular graph.

The Dijkstra's algorithm is stated below:

Let G=(V,E) be the simple graph. Let a and z be any two vertices on the graph. Let L(x ) denotes the label of the vertex x which represent the length of shortest path from the vertex a to the vertex x and wij which denotes the weight of the edge eij=

1.  Let P=φ where  P is the set of those vertices which

Are having permanent labels and T={all vertices in graph}

 

Set L(a)=0,

L(x)=∞ for all x≠a

 

2.

Select the

label. This

vertex v in T which has

label is called permanent

the smallest

label of v.

Also set P=P {v} and T=T-{v}

If v=z then L(z) is the length of the shortest path from the vertex a to z and stop.

3.  If  v is  not equal to z    then   revise      the   labels    of vertices of T that is the vertices which do not consist of permanent labels.

The new label of vertex x in T can be given by

L(x)=min(old L(x), L(v)+w(v, x))

Here w(v, x) is the weight of the edge joining the vertex v and x. If there exists no direct edge joining v and x then take w(v, x)= ∞

4.  Repeat steps 2 and 3 until get the permanent z label.

Posted Date: 7/10/2012 6:38:52 AM | Location : United States







Related Discussions:- Dijkstra's algorithm, Assignment Help, Ask Question on Dijkstra's algorithm, Get Answer, Expert's Help, Dijkstra's algorithm Discussions

Write discussion on Dijkstra's algorithm
Your posts are moderated
Related Questions
implement multiple stacks ina single dimensional array. write algorithams for various stack operation for them.

A linear collection of data elements where the linear node is given by means of pointer is known as Linked list

Program gives the program segment by using arrays for the insertion of an element to a queue into the multiqueue. Program: Program segment for the insertion of any element to t

In the last subsection, we have implemented a stack by using an array. While a stack is implemented by using arrays, it suffers from the basic restriction of an array - i.e., its s

H o w can you r ot a t e a B i n a r y Tr e e? E x pl a i n r i g h t a n d l eft r ot a tion s by taking an e x a mpl e.   If after

What is an Algorithm? An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for getting a needed output for any legitimate input in a finite amoun

algorithm for insertion in a queue using pointers

State the example of pre- and post-conditions Suppose that function f(x) should have a non-zero argument and return a positive value. We can document these pre- and post-condit

Explain the term - Branching There are two common ways of branching: case of ..... otherwise ...... endcase  if ..... then ..... else ..... endif   case of

#question bubble sort..