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
Example of pre order traversal: Reading of a book, since we do not read next chapter unless we complete all sections of previous chapter & all its sections. Figure  : Rea

Elaborate the symbols of abstract data type length(a)-returns the number of characters in symbol a. capitalize(a)-returns the symbol generated from a by making its first cha

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Assume a complete binary tree T with n nodes where each node has an item (value). Label the nodes of the complete binary tree T from top to bottom & from left to right 0, 1, ..., n

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

multilist representation of graph

A binary tree of depth "d" is an almost complete binary tree if  A) Every leaf in the tree is either at level "d" or at level "d-1"  B)  For any node "n" in the tree with a

i want to write code for unification algorithm with for pattern matching between two expression with out representing an expression as alist

Write an algorithm to print all even numbers in descending order and draw the flowchart

What is the difference between a grounded header link list and a circular header link list? A header linked list is a linked list which always having a special node, known as t