Dijkstra's algorithm, Data Structure & Algorithms

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


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



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
Program: Creation of Doubly Linked List OUTPUT Input the values of the element -1111 to come out : 1 Input the values of the element -1111 to come out : 2 Inpu

A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far left as possible, is called as

The number of leaf nodes in a complete binary tree of depth d is    2 d

After going through this unit, you will be able to: • define and declare Lists; • understand the terminology of Singly linked lists; • understand the terminology of Doubly

two standards ways of traversing a graph in data structure

Define about the inheritance hierarchy Languages Eiffel and D provide constructs in language for invariants and pre- and post conditions which are compiled into the code and ar

how to write a code for for a company , for calculate the salary pay

What are the conditions under which sequential search of a list is preferred over binary search?

Q. The degree of a node is defined as the number of children it has. Shear show that in any binary tree, the total number of leaves is one more than the number of nodes of degree 2

Five popular hashing functions are as follows: 1) Division Method 2) Midsquare Method 3) Folding Method 4) Multiplicative method 5) Digit Analysis