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
Write an algorithm to calculate a postfix expression.  Execute your algorithm using the given postfix expression as your input : a b + c d +*f ↑ . T o evaluate a postfix expr

Implementation of Stack :- Stacks can be executed in the 2 ways: a)  Arrays b)  Linked List

Circular Queues:- A more efficient queue representation is get by regarding the array Q(1:n) as circular. It becomes more convenient to declare the array as Q(O: n-1), when  re

A queue is a particular type of collection or abstract data type in which the entities in the collection are went in order and the principal functions on the collection are the add

what happen''s in my computer when i input any passage

Indexed Sequential Files An index is inserted to the sequential file to provide random access. An overflow area required to be maintained to permit insertion in sequence. I


What do you understand by term structured programming? Explain the structured programming as well.                                 Ans. S tructured Programming is expla

Since the stack is list of elements, the queue is also a list of elements. The stack & the queue differ just in the position where the elements may be added or deleted. Similar to

Since memory is becoming more & cheaper, the prominence of runtime complexity is enhancing. However, it is very much significant to analyses the amount of memory utilized by a prog