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
Objective The goal of this project is to extend and implement an algorithm presented in the course and to apply notions introduced by the course to this program/algorithm. The ass

Define the term 'complexity of an algorithm; Complexity of an algorithm is the calculate of analysis of algorithm. Analyzing an algorithm means predicting the resources that th

File organisation might be described as a method of storing records in file. Also, the subsequent implications approaching these records can be accessed. Given are the factors invo

A useful tool which is used for specifying the logical properties of a data type is called the abstract data type or ADT. The term "abstract data type" refers to the fundamental ma

This question deals with AVL trees. You must use mutable pairs/lists to implement this data structure: (a) Define a procedure called make-avl-tree which makes an AVL tree with o

(a) Write (delay ) as a special form for (lambda () ) and (force ), as discussed in class. (b) Write (stream-cons x y) as a special form, as discussed in class. (c) Write

What is Algorithm A finite sequence of steps for accomplishing some computational task. An algorithm should Have steps which are simple and definite enough to be done

The  total  of  time  needed  by  an algorithm to run to its completion is termed as time complexity. The asymptotic running time of an algorithm is given in terms of functions. Th

A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is called as a   Queue.

nested for loop for (i = 0; i for (j = 0; j sequence of statements } } Here, we observe that, the outer loop executes n times. Every time the outer loop execute